Count Strongly Connected Components
Two DFS passes: finish order on the graph, then components on its reverse
A component is a set of nodes that can all reach each other, so the hard part is telling 'reaches' apart from 'reaches AND is reached by'. Kosaraju's trick: run one DFS on the graph and record the order nodes FINISH in — a node finishes only after everything it can reach has already finished, so the last node to finish can reach no unfinished node above it in that order. Then reverse every edge and DFS again, popping nodes in that finish order. On the reversed graph, an edge that used to let a node escape its component now points back in, so each DFS from an unclaimed node can only sweep up its own component before running out of places to go.
Details
Animated on: 5 nodes, edges 0->1, 1->2, 2->0, 1->3, 3->4 — find every strongly connected component.
Problem:Count Strongly Connected ComponentsMedium
Two DFS passes: finish order on the graph, then components on its reverse
step 1 / 14
Directed graph
5 nodes, 5 directed edges. A strongly connected component is a set of nodes that can all reach each other — 0, 1 and 2 form a cycle here, so any two of them can reach one another, while 3 and 4 only ever get reached, never reach back.
1FUNCTION stronglyConnected(n, edges):2 adj, radj <- BUILD adjacency lists FROM edges AND reversed edges3 finishOrder <- empty stack4 FOR v FROM 0 TO n - 15 IF NOT visited1[v]6 DFS1(v, adj) THEN PUSH v TO finishOrder7 visited2 <- FALSE for every node8 components <- empty list9 WHILE finishOrder NOT EMPTY10 v <- POP finishOrder11 IF NOT visited2[v]12 component <- DFS2(v, radj)13 APPEND component TO components14 RETURN components
← / → step · space play · Home restart
Every step in words
Show all 14 steps
- 5 nodes, 5 directed edges. A strongly connected component is a set of nodes that can all reach each other — 0, 1 and 2 form a cycle here, so any two of them can reach one another, while 3 and 4 only ever get reached, never reach back.
- Pass 1 runs an ordinary DFS and remembers only WHEN each node finishes — every neighbour it can reach has already finished first. That finish order is the only thing pass 2 needs.
- Node 2 has nowhere left to go, so it finishes 1st and is pushed onto the finish stack: [2] (top first).
- Node 4 has nowhere left to go, so it finishes 2nd and is pushed onto the finish stack: [4, 2] (top first).
- Node 3 has nowhere left to go, so it finishes 3rd and is pushed onto the finish stack: [3, 4, 2] (top first).
- Node 1 has nowhere left to go, so it finishes 4th and is pushed onto the finish stack: [1, 3, 4, 2] (top first).
- Node 0 has nowhere left to go, so it finishes 5th and is pushed onto the finish stack: [0, 1, 3, 4, 2] (top first).
- Reverse every edge — an arrow into a component can no longer smuggle a node out of it, but every arrow inside a cycle still points somewhere inside it. Pop the finish stack top-first: 0, 1, 3, 4, 2.
- Starting from 0 on the transposed graph reaches {0, 2, 1} and nothing outside them — that whole set becomes component C1, exactly the cycle the reversed edges could not escape.
- Node 1 is already inside component C1 — a transposed-graph walk from it would only revisit nodes that component already owns, so skip it.
- Starting from 3 on the transposed graph reaches only itself — every neighbour it could reach was already claimed by an earlier component, so C2 is the single node {3}.
- Starting from 4 on the transposed graph reaches only itself — every neighbour it could reach was already claimed by an earlier component, so C3 is the single node {4}.
- Node 2 is already inside component C1 — a transposed-graph walk from it would only revisit nodes that component already owns, so skip it.
- RETURN 3 components: C1 = {0, 1, 2}, C2 = {3}, C3 = {4}. The highlighted edges are the ones that stayed inside their own component.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.