Count Strongly Connected Components (Kosaraju’s Algorithm)

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.

O(V + E), where ‘V’ and ‘E’ denote the number of vertices and edges in the graph, respectively.

We are traversing the complete graph twice where each traversal takes O(V + E) time. Finding the transpose of the graph takes O(V + E) time. Also, initialising the visited array takes O(V) time. Hence, the overall complexity is 2*O(V + E) + O(V + E) + O(V) = O(V + E).

O(V + E), where ‘V’ and ‘E’ denote the number of vertices and edges in the graph, respectively.

Extra space is required for the recursion stack. The maximum depth of the stack can be O(V). O(V) extra space is required for maintaining the stack and a visited array. Also, O(V+E) extra space is required for storing the adjacency list of the transpose graph. Hence, the overall space complexity is O(V) + O(V) + O(V) + O(V + E) = O(V + E).