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.

**Prerequisite:**

1. Arrival Time & Departure Time of Vertices in DFS

2. Types of edges involved in DFS and relation between them

In previous post, we have discussed a solution for that requires two DFS traversals of a Graph. We can check if graph is strongly connected or not by doing only **one DFS traversal of the graph**.

When we do a DFS from a vertex v in an directed graph, there could be many edges going out of its sub tree. When we say subtree rooted at v, we mean all v’s descendants including the vertex itself. The edges which are going out of the sub tree will either be a back edge or a cross edge. Forward edge cannot be going out of the sub tree as they can only be coming in to the sub tree or if it starts from within the sub tree it will go within the sub tree only.

**We can say that the graph is strongly connected if and only if for every edge u->v in the graph, there is at-least one back-edge or cross-edge that is going out of subtree rooted at v**.

##### How should we modify DFS so that we can check if there is a out-edge going out of every sub tree?

We can modify DFS such that DFS(v) returns the smallest arrival time to which there is an out-edge from the sub tree rooted at v. For example, let arrival(v) be the arrival time of vertex v in the DFS. Then if there is a edge out of the sub tree rooted at v, it’s to something visited before v & therefore with a smaller arrival value.

Remember for a back edge or cross edge u -> v,arrival[u] > arrival[v]

Suppose there are four edges going out of sub-tree rooted at v to vertex a, b, c and d and with arrival time arrival(a), arrival(b), arrival(c) and arrival(d) respectively. We look at their four arrival times & consider the smallest among them and that will be the value returned by DFS(v). i.e. DFS(v) returns min of arrival(a), arrival(b), arrival(c) and arrival(d). But before returning, we have to check that min(arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v). If min(arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v), then that means that at-least one back-edge or cross edge is going out of the sub tree rooted at v. If not, then we can stop the procedure and say that the graph is not strongly connected.

This is demonstrated below in C++:

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 <iostream> #include <vector> using namespace std; // data structure to store graph edges struct Edge { int src, dest; }; class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(const vector<Edge> &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the directed graph for (auto &edge: edges) adjList[edge.src].push_back(edge.dest); } }; // Perform DFS on graph starting from vertex v int DFS(Graph const &graph, int v, vector<bool> &discovered, int arrival[], bool& isSC, int &time) { // terminate the search if graph is not strongly // connected if (!isSC) return false; // set arrival time of vertex v arrival[v] = ++time; // mark vertex as discovered discovered[v] = true; // initialize arr to arrival time of vertex v int arr = arrival[v]; // do for every edge (v -> w) for (int w : graph.adjList[v]) { // vertex w is not yet explored if (!discovered[w]) arr = min(arr, DFS(graph, w, discovered, arrival, isSC, time)); // vertex w is explored before else // If the vertex is w is already discovered, // that means there is either a cross edge // or a back edge starting from v. Note that // the arrival time is already defined for w arr = min(arr, arrival[w]); } // if v is not root node and value of arr didn't // change i.e. it is still set to arrival time of // vertex v, the graph is not strongly connected if (v != 0 && arr == arrival[v]) isSC = false; // we return the minimum arrival time return arr; } // Check if given Graph is Strongly Connected or not 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} }; // Number of vertices in the graph int N = 5; // create a graph from given edges Graph graph(edges, N); // stores vertex is discovered or not vector<bool> discovered(N); // array to store arrival time of vertex. int arrival[N]; // flag to determine if graph is strongly connected // or not bool isSC = true; int time = -1; // Do DFS traversal starting from first vertex. DFS(graph, 0, discovered, arrival, isSC, time); // If DFS traversal doesn’t visit all vertices, // then graph is not strongly connected for (int i = 0; i < N; i++) if (discovered[i] == false) isSC = false; if (isSC) cout << "Graph is Strongly Connected"; else cout << "Graph is not Strongly Connected"; return 0; } |

`Output:`

Graph is Strongly Connected

The time complexity of above solutions is O(n + m) where n is number of vertices and m 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

Nice work 🙂