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.


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s