**Introduction**

A directed Graph is said to be strongly connected if there is a path between all pairs of vertices in some subset of vertices of the graph.

In simple words, it is based on the idea that if one vertex u is reachable from vertex v then vice versa must also hold in a directed graph. This strong connectivity is applicable for directed graphs only.

A naive approach of checking this property would be to look for whether we can traverse all vertices from every other vertex or not and such a method would lead to an tine complexity of O(V^{3}), where V is the number of vertices. There are two efficient ways of finding strongly connected components in a graph in linear time complexity.

- Kosarajuâ€™s Algorithm
- Tarjanâ€™s Algorithm

Recommended Topic, __binary search algorithm__

**Kosarajuâ€™s Algorithm**

Kosarajuâ€™s algorithm is just a DFS approach-based technique with a linear time complexity of O(V+E). But before jumping straight into the algorithm let us first define a Condensed Component Graph as a graph with <=V nodes and <=E edges in which every node is Strongly Connected Component. It can be proved that a condensed component graph is a directed acyclic graph. Letâ€™s prove it by contradiction and assume that it is not directed acyclic.

Now letâ€™s observe that on the cycle, every strongly connected component can reach every other strongly connected component via a directed path, which in turn means that every node on the cycle can reach every other node in the cycle, because in a strongly connected component every node can be reached from any other node of the component. So if there is a cycle, the cycle can be replaced with a single node because all the Strongly Connected Components on that cycle will form one Strongly Connected Component. Therefore, the Condensed Component Graph will be a DAG.

Observe that if a DFS is done from any node in the Sink, only nodes in the Strongly Connected Component of Sink are visited. Now, removing the sink also results in a DAG, with maybe another sink.

So the above process can be repeated until all Strongly Connected Componentâ€™s are discovered. So at each step any node of Sink should be known. This should be done efficiently. Thus algorithm can be pointed out as follows:

- Do a DFS traversal of original graph and keep track of finish time of every node. Sort the nodes according to finishing time in descending order. To perform this we can use stack. This way the node with highest finishing time will be on top of the stack.
- Reverse the original graph.
- Start another DFS traversal with the source vertex being the vertex on top of the stack. Pop vertices from top of the stack until a valid unvisited vertex are found. These steps are repeated until all nodes are visited. When this DFS call finishes all nodes that are a part of strongly connected component will be visited.

A C++ snippet of the code of the three steps described above is given below:

The following method should be called in main before step 3.

Also see, __floyd's algorithm__