Strongly Connected Components

A directed graph is strongly connected if there is a path from every vertex to all the other vertices in the graph.

The strongly connected components (SCCs) of a graph divide the graph into strongly connected parts as large as possible. For example consider the following graph:

Its strongly connected components are:

The corresponding component graph is:

The components are `A = {1,2}, B = {3,6,7}, C = {4} and D = {5}.

A component graph is always a directed acyclic graph or DAG.

The number of SCCs in a graph can be computed using Kosaraju’s Algorithm which uses two DFS traversals (one of the original graph and the other of the transposed graph).

Pseudocode to get the number of SCCs in a graph:

DFS(graph,u,type)
{
# type = 1 => fill the stack as well along with traversal
# type = 2 => simple DFS traversal
	if(visited[u]) return; 
	else visited[u] = true; 
	for every neighbour v of u:
		DFS(graph,v,type);
		
# now push u to the stack after pushing every reachable vertex from it.
	if(type == 1)
	Stack.push(u); 
}
	
countSCC(graph)
{
	count = 0;
	stack Stack ;
	visited[V] = {false};
	for every node u in graph:
		DFS(graph,u,type=1);
	Graph gT = transpose(graph);
	visited[V] = {false};
	while Stack is not Empty:
		u = Stack.top();
		Stack.pop();
		if(!visited[u]):
			DFS(gT,u,type=2);
			count++;
	return count;
}	

References: GeeksforGeeks