Kosaraju's algorithm finds all Strongly Connected Components (SCCs) — maximal subgraphs where every vertex is reachable from every other vertex — in O(V+E) time. It runs DFS on the original graph to get finish-time ordering, then DFS on the transposed graph in reverse finish-time order.
void dfs1(int v,vector<vector<int>>& g,vector<bool>& vis,stack<int>& st){
vis[v]=true;
for(int u:g[v]) if(!vis[u]) dfs1(u,g,vis,st);
st.push(v);
}
void dfs2(int v,vector<vector<int>>& rg,vector<bool>& vis,vector<int>& comp){
vis[v]=true; comp.push_back(v);
for(int u:rg[v]) if(!vis[u]) dfs2(u,rg,vis,comp);
}
vector<vector<int>> kosaraju(int n,vector<vector<int>>& g){
vector<bool> vis(n,false); stack<int> st;
for(int i=0;i<n;i++) if(!vis[i]) dfs1(i,g,vis,st);
vector<vector<int>> rg(n);
for(int u=0;u<n;u++) for(int v:g[u]) rg[v].push_back(u);
fill(vis.begin(),vis.end(),false);
vector<vector<int>> sccs;
while(!st.empty()){int v=st.top();st.pop();
if(!vis[v]){vector<int> comp;dfs2(v,rg,vis,comp);sccs.push_back(comp);}}
return sccs;
}An SCC is a maximal set of vertices where every vertex can reach every other vertex. Every directed graph can be decomposed into SCCs, which form a DAG (the condensation graph).
Run DFS on the original graph. Push each vertex onto a stack when DFS finishes processing all its descendants. This gives vertices in reverse topological order of the SCC DAG.
Transpose the graph (reverse all edges). Process vertices from the stack (highest finish time first). Each DFS tree in the transposed graph is exactly one SCC.
If u can reach v in the original graph and v can reach u, then they are in the same SCC. Transposing reverses all paths. The finish-time ordering ensures each SCC is discovered separately.
Quiz coming soon for this algorithm.