In a directed graph, edges are one-way, so A reaching B says nothing about B reaching A. A strongly connected component (SCC) is a maximal group of vertices where everyone can reach everyone — follow the arrows from any vertex in the group and you can get to any other, and back. Kosaraju's algorithm finds all of them in two depth-first passes.
The two-pass trick
The magic is in *reversing the graph*. The first DFS records the finish order — the order vertices run out of unexplored neighbours. The second DFS runs on the transpose (every edge flipped), processing vertices in *reverse* finish order. Reversing the edges traps each mutually-reachable group inside its own search tree, so each tree the second pass carves out is exactly one SCC.
1Pass 1 — run DFS over the original graph; when a vertex finishes (all neighbours explored), push it onto a stack. This records the finish order.
2Build the transpose — reverse the direction of every edge.
3Pass 2 — pop vertices off the stack (reverse finish order) and DFS each in the transpose graph.
4Every vertex reached in one such DFS forms one SCC; start a new component for the next unvisited vertex popped.
Why reversing edges confines each group
Within an SCC every vertex reaches every other in *both* directions, so flipping edges leaves the SCC just as internally connected. But edges *between* different SCCs all get flipped to point the 'wrong' way — so a second DFS, started in the right (reverse-finish) order, can fill one SCC and no further, because the only outward edges now lead back to already-finished components.
Pass 1 (original graph): DFS, push each vertex on finish
finish stack (top = last finished): [ A, B, C, ... ]
Reverse every edge -> transpose graph
Pass 2 (transpose): pop in reverse finish order, DFS each
pop A -> DFS reaches {A, ...} = SCC 1
pop next unvisited -> DFS reaches {...} = SCC 2
...one search tree = one component
Kosaraju vs Tarjan
Kosaraju's two passes are the easiest to picture, but they scan the graph twice and build the transpose. Tarjan's algorithm finds the same SCCs in a *single* DFS using discovery numbers and a stack — same O(V + E), one pass, no reversed graph.
OperationTimeSpace
Kosaraju (two DFS passes) · second pass on the transposed graphO(V + E)O(V + E)
Check yourself
Why does Kosaraju's second DFS run on the graph with all edges reversed?
