Strongly Connected Components -

Strongly Connected Components are maximally sized components in directed graphs such that every node in a component can reach every other node.

This is a strongly connected component since every node can reach every other node.

This is not a strongly connected component since 5 cannot reach 7.

Kosaraju’s algorithm splits a directed graph into maximally sized strongly connected components.

An example of a directed graph split into maximally sized strongly connected components (SCC).

An important fact is that if we condense each SCC into a node and draw edges connected SCC’s, then the graph will form a directed acyclic graph. This is true because if there was indeed a cycle in the new graph, then it would form another SCC which contradicts the maximally sized condition.

Kosaraju’s algorithm takes advantage of the following fact: If you reverse all the edges in a graph the strongly connected components won’t change. We are simply mirroring the graph.

So we will construct a transposed graph which is just the original graph except all edges are reversed.

Firstly we will perform DFS on every node in the original graph, and sort them by their exit times. Notice that the last node is guaranteed to be in an SCC that has no outgoing edges to other SCC’s, so we’re essentially topologically sorting the compressed SCC’s in reverse order. Then in the second pass, we will iterate in decreasing order of exit times. Each time we will fully DFS to find a strongly connected component. The property that all nodes are reachable from all other nodes in an SCC means that we will underadd any nodes or over add any nodes.

//1 indexed
const int N = 10;
vector<vector<int>> adj(N+1);
vector<vector<int>> revadj(N+1);
vector<bool> vis(N+1); vector<int> id(N+1); //id will store which SCC the node belongs to
vector<int> ord;

void dfs(int v){
vis[v] = true;
for(int u : adj[v]){
if(!vis[u]){
dfs(u);
}
}
ord.push_back(v);
}

void dfs1(int v){
vis[v] = true;
for(int u : revadj[v]){
if(!vis[u]){
id[u] = id[v];
dfs1(u);
}
}
}

void findSCC(){
for(int i = 1; i <= N; i++){
if(!vis[i])dfs(i);
}
fill(vis.begin(), vis.end(), false);
int cnt = 1; reverse(ord.begin(), ord.end());
for(int i = 0; i < N; i++){
if(!vis[ord[i]]){
id[ord[i]] = cnt++;
dfs1(ord[i]);
}
}
}