Strongly Connected Components (Kosaraju)
Split a directed graph into strongly connected components — maximal groups where every vertex reaches every other.
- 1 <= V <= 10⁵
- 0 <= E <= 10⁵
- Graph is directed; two passes are needed, the second on the transpose
Intuition
Strongly connected components kosaraju splits a directed graph into maximal groups where every vertex can reach every other. Kosaraju's algorithm does it with two depth-first passes, and the reason it works is genuinely clever. A plain DFS cannot isolate components on its own, because it happily runs out of one component and into another through a one-way edge. The first pass records finish times on the original graph, pushing each vertex onto a stack as it completes. The vertex finishing last belongs to a component with no incoming edges from anywhere else — a source in the condensation, the DAG formed by contracting each component to a point. The second pass runs on the reversed graph, and this is where the idea lands: - Reversing every edge leaves each component internally unchanged — mutual reachability is symmetric — but flips the one-way links between components. So a DFS started in a source component on the reversed graph can no longer escape it: the edges that used to lead out now lead in. Whatever it reaches is exactly one strongly connected component. Pop vertices off the stack in finish-time order, and each unvisited one starts a DFS whose reachable set is precisely its component. Tarjan's algorithm reaches the same result in a single pass using low-link values. Kosaraju's is two passes but far easier to explain, which is usually the better trade in an interview.
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
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V + E) space.
Understand why one DFS is not enough
A plain traversal runs out of one component and into another through a one-way edge, so its reachable set is not a component. The two passes exist to fence the traversal in, and knowing that motivates everything below.
Pass one: record finish order
Run DFS on the original graph, pushing each vertex onto a stack when it finishes, not when it is discovered. Later finishers belong to components earlier in the condensation DAG.
Build the transpose graph
Reverse every edge: u → v becomes v → u. Mutual reachability inside a component is unaffected — if two vertices reach each other, they still do — but the one-way links between components now point the other way.
Pass two: DFS in reverse finish order
Pop vertices from the stack; each unvisited one starts a DFS on the reversed graph. Its reachable set is exactly one strongly connected component, because the reversal blocks the escape routes the original edges provided.
Collect each tree as a component
Every DFS tree grown in the second pass is one component. Vertices already visited are skipped, so each belongs to exactly one component and the partition is complete.
Compare with Tarjan's algorithm
Tarjan's finds the same components in one pass using low-link values and an explicit stack. It is faster by a constant factor but harder to explain; Kosaraju's two-pass structure is usually the better interview answer.
Cost of the two passes
Each pass visits every vertex and edge once, and building the transpose is O(V + E), giving O(V + E) time overall with O(V + E) space for the reversed graph and the stack.
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.