Kosaraju's Algorithm (Strongly Connected Components)
WHAT IT SAYS
Partition a directed graph into its strongly connected components — maximal groups where every vertex reaches every other.
WHAT IT'S REALLY ASKING
"A DFS launched anywhere overshoots: it consumes its component AND everything downstream. The fix is a pincer: reversing every edge keeps each SCC intact (mutual reachability is symmetric) but flips which way the between-component arrows point — so a traversal that WOULD have leaked downstream now finds those exits walled off. Order the launches by first-pass finish times, and each reversed-graph DFS is trapped inside exactly one component."
Test mutual reachability pairwise
O(V · (V + E)) at best — a reachability sweep per vertexFor each vertex pair (u, v), check u ⇝ v and v ⇝ u by two searches; group vertices whose mutual reachability holds — or per vertex, intersect its forward-reachable set with its backward-reachable set to get its component.
WHERE THE WORK IS WASTED — Mutual reachability is an equivalence relation, and the pairwise method verifies it retail: vertices in one 50-member SCC have their co-membership certified 50 times over by overlapping searches that walk the same cycles repeatedly. The intersection framing (forward-set ∩ backward-set per vertex) leaks the key ingredient — the REVERSED graph computes backward reachability — but deploys it per vertex, re-traversing shared structure once per member. The components partition the graph; a partition should be enumerable at one-launch-per-class, like Provinces — the entire difficulty is that directed edges let a launch escape its class, and THAT is the problem to solve, not reachability itself.
Finish order finds the sources; reversal turns them into prisons.
Zoom out to the CONDENSATION: contract each SCC to a single super-node, keep the between-component edges. The condensation is always a DAG — a cycle among super-nodes would merge them into one SCC, contradiction. Now the overshoot problem has a name: a DFS launched in super-node X consumes X and everything X can reach in the DAG. A launch is clean only if its component has NO exits — a SINK of the condensation. So the plan: find a sink component, consume it, remove it, repeat. Two obstacles: identifying sinks without knowing the components (circular), and 'removing' consumed vertices. Kosaraju dissolves both with two classical facts. Fact one — finish times locate sources: run any full DFS (pass one) and record each vertex's finishing time; then the vertex finishing LAST in the entire graph lies in a SOURCE component of the condensation. The argument: if component A has an edge to component B in the DAG, then A's maximum finish time exceeds B's — either the DFS entered A first (it then explores into B and B finishes while A is still open) or it entered B first (B finishes entirely before A is even started, since B cannot reach back into A — the DAG has no reverse edge). Either way A finishes later. So decreasing finish order lists components in a topological order of the condensation: sources first. Fact two — reversal flips the DAG but fixes the components: reversing every edge preserves each SCC exactly (u ⇝ v and v ⇝ u swap roles — mutual reachability is symmetric) while every between-component arrow flips, turning the condensation's sources into SINKS. Compose them: process vertices in decreasing pass-one finish time, launching pass-two DFS on the REVERSED graph. The first launch starts in a source-of-original = sink-of-reversed component: the traversal consumes it and cannot leave — every exit is walled. Later launches start at the highest-finishing unvisited vertex, which by the topological ordering lies in a source among the REMAINING components; its only reversed-graph exits lead into components already consumed and marked visited — the visited array is the 'removal'. Each launch harvests exactly one SCC; the launches enumerate the partition, Provinces-style, with the escape problem solved by the pincer of ordering plus reversal. Two passes, one reversal, O(V + E).
DFS for finish order, reverse, DFS again in that order
O(V + E) time — two traversals plus one reversal — O(V + E) space for the reversed graphPass one: full DFS over the original graph, pushing each vertex onto a stack at FINISH (post-order); launch from every unvisited vertex. Build the reversed adjacency list. Pass two: reset visited; pop the stack, and for each unvisited vertex launch a DFS on the reversed graph — every vertex reached in that launch belongs to one SCC; collect and continue. Iterative DFS for deep graphs.
Order the Launches, Wall the Exits
YOU'LL SEE IT AGAIN WHEN
- The classes of an equivalence (mutual reachability) must be enumerated, but a naive launch consumes its class PLUS everything downstream.
- Post-order finish times topologically order the classes — the last finisher always sits in a source of the condensation.
- The transformation that preserves classes but flips between-class edges (reversal) turns sources into escape-proof sinks — launch there.