Strongly Connected Components (Kosaraju)
Split a directed graph into strongly connected components — maximal groups where every vertex reaches every other.
Open on GeeksforGeeks ↗Intuition
Two DFS passes. The first records finish times on the original graph; the last vertex to finish must sit in a 'source' component. Reversing every edge preserves each component internally but flips the one-way links between them — so a DFS on the reversed graph, started in finish-time order, can no longer escape a component. Each tree it grows is exactly one SCC.
Two DFS passes with the edges reversed between them. The first pass records finish times; the second, run on the transpose in reverse finish order, can't escape the component it starts in. Reversing the edges is what confines each traversal — the exit routes become entrances.
Approach
Pass 1 — order by finish time
Run DFS on the original graph, pushing each vertex onto a stack when it finishes. Later finishers belong to components that come earlier in the condensed DAG.
Reverse the graph
Build the transpose: every u → v becomes v → u. Mutual reachability inside a component is unaffected, but the edges connecting different components now point the other way.
Pass 2 — DFS in reverse finish order
Pop vertices off the stack; each unvisited one starts a DFS on the reversed graph whose reachable set is precisely its SCC — the reversal blocks it from leaking into neighbouring components.
Solution & live demo
Common pitfalls
Using the original graph in the second pass
dfs2(v, comp) over adj
dfs2(v, comp) over radj
On the original graph a DFS from the latest-finishing vertex leaks into downstream components and merges them all into one. Reversing the edges makes those exits unusable, so the traversal is trapped inside a single SCC.
Processing pass two in finish order rather than reverse
for v in order:
for v in reversed(order):
The correctness argument needs the vertex that finished last to go first, since it belongs to a source component of the condensation. Forward order starts in a sink and the same merging problem returns.
Appending to the order before recursing
order.append(v) for u in adj[v]: ...
for u in adj[v]: ... order.append(v)
That records discovery time, not finish time, and the two give different orderings. Kosaraju depends specifically on finish order, so the append must come after all recursive calls return.
Edge cases
Pass 2 finds one component containing everything.
Every vertex is its own component — V components.
Each piece contributes its own components; the outer loops cover all.