Count Strongly Connected Components (Kosaraju’s Algorithm)

Posted: 18 Feb, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an unweighted directed graph having 'V' vertices and 'E' edges. Your task is to count the number of strongly connected components (SCCs) present in the graph.

A directed graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a graph are the subgraphs which are themselves strongly connected.

Note :
Use zero-based indexing for the vertices.

The given graph doesn’t contain any self-loops.
Input Format :
The very first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of every test case contains two space-separated integers ‘V’ and ‘E’ denoting the number of vertices and the number of edges present in the graph. 

The next ‘E’ lines contain two space-separated integers ‘a’ and ‘b’ denoting a directed edge from vertex ‘a’ to ‘b’.
Output Format :
For each test case, return an integer denoting the number of strongly connected components (SCCs) present in the graph.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= V <= 10^4
0 <= E <= 10^4
0 <= a, b < V

Time Limit: 1 sec
Approach 1

Kosaraju’s algorithm can find the strongly connected components (SCCs) of a graph in linear time.

  • The idea behind this algorithm is to use the finish time of the vertices to generate the SCCs.
  • The finish time of a vertex is the time at which the exploration of the vertex completes.
  • Let’s assume that the finish time for an SCC is the maximum of the finish time of all the vertices present in that SCC. Then the finish time of an SCC which is connected to any other SCC will always be greater than the finish time of the other SCC. (You can refer here for the proof).
  • In order to determine the finish times of the vertices, we traverse the graph once. During the traversal, if the exploration of a vertex completes, we push the vertex in a stack.
  • This gives us the nodes in descending order of their finish times, as the node with a larger finish time will be present closer to the top of the stack.
  • For example, consider the graph below. After traversing the graph once, we have the nodes stored in the stack in descending order of their finish time. The starting and the finish time for the vertices are shown above each vertex as <start time, finish time>.
  • The topmost vertex of the stack will belong to the SCC which has the largest finish time and this SCC will be the ‘root’ node of the condensation graph (A condensation graph of a directed graph G is a directed graph G', whose vertices are strongly connected components of G, and the edge in G' is present only if there exists at least one edge between the vertices of corresponding connected components).
  • Now we want to visit all the SCCs one by one. If we travers the graph starting from the top node of the stack, we will visit all the vertices of the graph and won’t be able to distinguish different SCCs. So, we compute the transpose of the graph by reversing the direction of every edge.
  • This way the SCCs of the graph remain the same but their order gets reversed i.e. the condensation graph gets reversed.
  • Now, if we start the traversal from the topmost vertex in the stack, then we only visit the vertices belonging to the same SCC, i.e. SCC 1 here.
  • We pop the topmost vertex from the stack and repeat the previous step for the remaining unvisited vertices.
  • In this way, SCC 2 and 3 also are visited and we generate all the SCCs of the graph.

Algorithm:

  • Create an empty stack to store the vertices in descending order of their finished time.
  • Create a visited array of size ‘V’ and initialize all the entries to false.
  • Loop: For ‘i’ in the range 0 to V-1:
    • Apply DFS considering ‘i’ as source vertex. While performing DFS we keep track of which vertices have been visited by updating the visited array. As the exploration of vertices present in the DFS tree of ‘i’ is completed, we push them into the stack
  • Get the transpose of the given graph by reversing the direction of every edge.
  • Mark all the vertices as unvisited.
  • Create a variable count to store the count of the SCCs.
  • Repeat the following steps until the stack becomes empty:
    • Pop the top vertex from the stack and store it in a variable say, ‘V’.
    • If the vertex ‘V’ is not visited before:
      • Apply DFS, taking ‘V’ as the source vertex. While performing DFS keep track of which vertices have been visited by updating the visited array.
      • Increment ‘COUNT’ by one.
  • Return ‘COUNT’.

Note:

In the above approach, we have used DFS. You can also use BFS, but the idea will remain the same.

Try Problem