Strongly Connected Components¶

In a directed graph, vertices u and v belong to the same strongly connected component (SCC) when each can reach the other. SCCs partition the vertices.

Contract every SCC to one meta-vertex. The resulting condensation graph is a directed acyclic graph: a cycle among components would make them mutually reachable and therefore one component.

Kosaraju–Sharir¶

Run DFS and record vertices by finish time.
Reverse every edge.
Process vertices in decreasing original finish time, running DFS in the reversed graph. Each new traversal yields one SCC.

Both traversals and reversal cost Θ(V + E) time, with Θ(V + E) additional storage when the transpose is materialized.

Tarjan¶

Tarjan's algorithm uses one DFS, a stack, discovery indices, and low-link values. A vertex roots an SCC when its low-link equals its discovery index; the stack is popped through that root. It also runs in Θ(V + E) time and uses Θ(V) working space beyond the graph.

Low-link is not merely the minimum neighbor number. Its update distinguishes a DFS-tree edge from an edge to a vertex still on the active stack.

Applications¶

SCCs expose cycles of mutual dependency, permit topological processing of a directed graph's condensation, and support reachability and program-analysis decompositions.

Exercises¶

Prove that the condensation graph is acyclic.
Trace both algorithms on a graph with three SCCs.
Explain why connected components are insufficient for directed graphs.