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.
Problems to try:
SPOJ – WEBISL
SPOJ – CAPCITY
SPOJ – BOTTOM
SPOJ – TPCPPLAR
Codeforces Round#244 Div2 C
References:
Kosaraju algorithm Wikipedia
Strongly connected component geeksforgeeks.org
