## Finding Strongly Connected Component

What is a strongly connected component?

A strongly connected component or SCC of a directed graph is a maximal set of vertices’s in which there is a path from any one vertex to any other vertex in the set. Or in other words it is a maximal strongly connected subgraph.

Finding strongly connected components is a simple application of Depth First Search in Directed graphs.
For example there are 3 SCC in the given graph

Reverse/Transpose graph: It is a directed graph with the direction of all its edges reversed. This usually comes handy while dealing with problems involving topological sort.

We can find all SCC using Kosaraju’s 2 pass algorithm for finding the strongly connected component in a directed graph in O(n+m) time complexity. I prefer this algorithm because it is prevalent and quite easy to understand and code as well in programming contest environment.

Kosaraju’s algorithm is as follows:

• Let G be a directed graph and S be an empty stack.
• While S does not contain all vertices:
• Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
• Reverse the directions of all arcs to obtain the transpose graph.
• While S is nonempty:
• Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

The main idea for using transpose graphs in this algorithm is

Graphs G and G’ have the same SCC’s

Also , the SCC component graph is a directed acyclic graph.

The C++ implementation to the above algorithm can be found here.