Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

For example, below graph is strongly connected as path exists between all pairs of vertices

A simple solution would be to perform DFS or BFS starting from every vertex in the graph. If each DFS/BFS visits every other vertex in the graph, the graph is strongly connnected.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 5 // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the directed graph for (unsigned int i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; adjList[src].push_back(dest); } } }; // Function to perform DFS Traversal void DFS(Graph const &graph, int v, vector<bool> &discovered) { // mark current node as discovered discovered[v] = true; // do for every edge (v -> u) for (int u : graph.adjList[v]) { // u is not discovered if (!discovered[u]) DFS(graph, u, discovered); } } // check if graph is strongly connected or not bool check(Graph const& graph) { // do for every vertex for (int i = 0; i < N; i++) { // stores vertex is discovered or not vector<bool> discovered(N); // start DFS from first vertex DFS(graph, i, discovered); // If DFS traversal doesn’t visit all vertices, // then graph is not strongly connected if (find(discovered.begin(), discovered.end(), false) != discovered.end() ) return false; } return true; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 4}, {1, 0}, {1, 2}, {2, 1}, {2, 4}, {3, 1}, {3, 2} , {4, 3} }; // create a graph from given edges Graph graph(edges); // check if graph is not strongly connected or not if (check(graph)) cout << "Graph is Strongly Connected"; else cout << "Graph is not Strongly Connected"; return 0; } |

**Output: **

Graph is Strongly Connected

**Time complexity**of above solution is O(n(n + m)) where n is number of vertices and m is number of edges in the graph.

**Can we do better?**

We can say that G is strongly connected if

1. DFS(G, v) visits all vertices in graph G, then there exists path from v to every other vertex in G and

2. There exists a path from every other vertex in G to v

**Proof:**

For G to be strongly connected, there should exists a path from x -> y and from y -> x for any pair of vertices (x, y) in the graph.

If Point 1 and Point 2 are true,

We can reach x -> y by going from vertex x to vertex v (from pt. 2) and then from vertex v to vertex y (from pt. 1).

Similarly, we can reach y -> x by going from vertex y to vertex v (from pt. 2) and then from vertex v to vertex x (from pt. 1).

**Complete Algorithm – **

1. Start DFS(G, v) from a random vertex v of the graph G. If DFS(G, v) fails to reach every other vertex in the graph G, then there is some vertex u, such that there is no directed path from v to u, and thus G is not strongly connected. If it does reach every vertex, then there is a directed path from v to every other vertex in the graph G.

2. Reverse the direction of all edges in the directed graph G.

3. Again run a DFS starting from vertex v. If the DFS fails to reach every vertex, then there is some vertex u, such that in the original graph there is no directed path from u to v. On the other hand, if it does reach every vertex, then in the original graph there is a directed path from every vertex u to v.

Thus, if G passes both DFSs, it is strongly connected.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 5 // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the directed graph for (unsigned int i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; adjList[src].push_back(dest); } } }; // Function to perform DFS Traversal void DFS(Graph const &graph, int v, vector<bool> &discovered) { // mark current node as discovered discovered[v] = true; // do for every edge (v -> u) for (int u : graph.adjList[v]) { // u is not discovered if (!discovered[u]) DFS(graph, u, discovered); } } // check if graph is strongly connected or not bool check(Graph const& graph) { // stores vertex is discovered or not vector<bool> discovered(N); // choose random starting point int v = 0; // run a DFS starting at v DFS(graph, v, discovered); // If DFS traversal doesnâ??t visit all vertices, // then graph is not strongly connected if (find(discovered.begin(), discovered.end(), false) != discovered.end() ) return false; // reset discovered vector fill(discovered.begin(), discovered.end(), false); // Reverse the direction of all edges in the // directed graph vector<Edge> edges; for (int i = 0; i < N; i++) for (int j : graph.adjList[i]) edges.push_back({j, i}); // Create a graph from reversed edges Graph gr(edges); // Again run a DFS starting at v DFS(gr, v, discovered); // If DFS traversal doesnâ??t visit all vertices, // then graph is not strongly connected if (find(discovered.begin(), discovered.end(), false) != discovered.end() ) return false; // if graph "passes" both DFSs, it is strongly connected return true; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 4}, {1, 0}, {1, 2}, {2, 1}, {2, 4}, {3, 1}, {3, 2}, {4, 3} }; // create a graph from given edges Graph graph(edges); // check if graph is not strongly connected or not if (check(graph)) cout << "Graph is Strongly Connected"; else cout << "Graph is not Strongly Connected"; return 0; } |

**Output: **

Graph is Strongly Connected

**Time complexity** of above solution is O(n + m) where n is number of vertices and e is number of edges in the graph. Please note that O(m) may vary between O(1) and O(n^{2}), depending on how dense the graph is.

**Reference:** Dr. Naveen garg, IIT-D (Lecture – 30 Applications of DFS in Directed Graphs)

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply