Two passes
Kosaraju's algorithm finds strongly connected components using two depth first searches. The first pass orders nodes by finish time; the second pass explores the reversed graph in decreasing finish order, and each tree it grows is one component.
Why reversing works
Reversing every edge keeps each strongly connected component intact, because mutual reachability is symmetric. But reversal cuts the one way links between different components. Starting the second pass from the latest finishing node ensures the search stays inside a single component before it can leak into another.
- First pass: record finish order on the original graph.
- Reverse all edges.
- Second pass: in decreasing finish order, each search tree is a component.
Key idea
Kosaraju finds strongly connected components with two depth first passes: one to order nodes by finish time and one on the reversed graph in that order, where each search tree marks a single component.