Strongly Connected Components

A directed graph $G = (V, E)$ has vertices $u$ and $v$ that are strongly connected if there is a path from $u$ to $v$ and a path from $v$ to $u$. Strong connectivity is an equivalence relation on $V$: it is reflexive (a vertex trivially reaches itself), symmetric by definition, and transitive (if $u \leftrightarrow v$ and $v \leftrightarrow w$ then $u \leftrightarrow w$ by concatenating paths). Because it is an equivalence relation, it partitions $V$ into disjoint equivalence classes — these classes are the strongly connected components of $G$. Each SCC is a maximal subset of vertices that are pairwise mutually reachable. Given the SCCs $C_1, \dots, C_k$, define the component graph $G^{SCC}$ by contracting each $C_i$ to a single supernode, and drawing an edge $C_i \to C_j$ whenever some edge in $G$ goes from a vertex in $C_i$ to a vertex in $C_j$ (for $i \ne j$). A short argument shows $G^{SCC}$ is always acyclic: if $G^{SCC}$ had a cycle through supernodes $C_{i_1} \to C_{i_2} \to \dots \to C_{i_1}$, then every vertex in every $C_{i_j}$ could reach every vertex in every other $C_{i_j}$ through this cycle, forcing them all into one SCC — contradicting that the $C_{i_j}$ were distinct maximal components. This acyclicity is exactly why Topological Sort applies to the component graph once it is built, and why SCC decomposition is often the first preprocessing step before running DAG-based scheduling algorithms. Kosaraju's algorithm exploits DFS Edge Classification and Timestamps with a clever twist: it runs DFS twice, once forward on $G$ and once backward on the transpose graph $G^T$ (same vertex set, every edge reversed). Note that $G$ and $G^T$ have exactly the same SCCs, since reversing every edge reverses every path, so mutual reachability is preserved. The key insight — proved in the next section — is that if you process vertices in the second DFS in decreasing order of their finish times from the first DFS, each resulting DFS tree in the forest is precisely one SCC.

The algorithm has three phases: a DFS on $G$ recording finish times, a transposition of the graph, and a DFS on $G^T$ visiting vertices in decreasing finish-time order.

Phase 1. Run DFS on $G$. Every time a vertex's adjacency list is exhausted (its DFS call is about to return), stamp it with a finish time and push it onto a stack (or append to a list). The vertex finishing last ends up on top.

Phase 2. Build $G^T$ by reversing every edge of $G$. If $G$ is given as adjacency lists, this takes $O(V+E)$ time: scan every edge $(u,v)$ once and insert $(v,u)$ into $G^T$'s adjacency list.

Phase 3. Run DFS on $G^T$, but choose the next unvisited root strictly in decreasing order of the Phase 1 finish times (equivalently, pop vertices off the stack built in Phase 1). Each tree produced by this DFS forest is output as one strongly connected component. ``` KOSARAJU-SCC(G): // Phase 1: DFS on G, record finish order for each vertex u in G.V: u.visited = false finishOrder = empty stack for each vertex u in G.V: if not u.visited: DFS-VISIT-1(G, u, finishOrder) // Phase 2: build transpose G_T = TRANSPOSE(G) // Phase 3: DFS on G_T, in decreasing finish order for each vertex u in G_T.V: u.visited = false components = empty list while finishOrder is not empty: u = finishOrder.pop() if not u.visited: newComponent = empty set DFS-VISIT-2(G_T, u, newComponent) components.append(newComponent) return components

DFS-VISIT-1(G, u, finishOrder): u.visited = true for each v in G.adj[u]: if not v.visited: DFS-VISIT-1(G, v, finishOrder) finishOrder.push(u) // stamp finish time by push order

DFS-VISIT-2(G_T, u, component): u.visited = true component.add(u) for each v in G_T.adj[u]: if not v.visited: DFS-VISIT-2(G_T, v, component)

TRANSPOSE(G): G_T = new graph with same vertices as G, no edges for each vertex u in G.V: for each v in G.adj[u]: G_T.adj[v].add(u) return G_T ``` Every vertex is visited exactly once in each DFS pass, and every edge is examined exactly once per pass (once in $G$, once in $G^T$), so both DFS phases and the transpose construction are linear in the size of the graph.

The diagram shows the essential shape: $G$ has three SCCs (the blue triangle $\{A,B,C\}$, the orange triangle $\{D,E,F\}$, and the singleton $\{G\}$), the component graph collapsing them is a simple chain (hence acyclic), and the finish stack from Phase 1 always places a vertex of the "last" SCC in the topological order ($\{A,B,C\}$, the source of the DAG) on top, guaranteeing it is popped first in Phase 3.

Running time. Let $n = |V|$ and $m = |E|$. Phase 1 is a standard DFS: $O(n+m)$. Building $G^T$ scans every edge once: $O(n+m)$. Phase 3 is another standard DFS over $G^T$, which has the same number of vertices and edges as $G$: $O(n+m)$. Summing three linear phases gives total time

which is asymptotically optimal — any correct algorithm must at least read the input. Space is $O(n+m)$ for the adjacency lists of $G$ and $G^T$, plus $O(n)$ for the finish-time stack, visited flags, and recursion stack.

Correctness — the component-DAG argument. The proof rests on one key lemma about DFS finish times applied to the component graph. Lemma (finish-time ordering across components). Let $C$ and $C'$ be distinct SCCs of $G$, and suppose there is an edge from some vertex of $C$ to some vertex of $C'$ in $G^{SCC}$ (i.e., $C \to C'$). Let $f(C)$ denote the maximum finish time, over a DFS of $G$, of any vertex in $C$. Then

Proof sketch. Consider whichever of $C$ or $C'$ is discovered first by the DFS, and let $x$ be the first vertex discovered among $C \cup C'$.

• Case 1: $x \in C$. Since $C \to C'$ and (because $G^{SCC}$ is acyclic) there is no edge back from $C'$ to $C$, every vertex of $C'$ reachable from $x$ is reached via some path leaving $C$ that never returns. At the moment $x$ is discovered, all of $C$ and all of $C'$ reachable from $C$ are still white, so by the white-path property of DFS, $x$'s DFS subtree will finish after completely exploring both $C$ and $C'$ (since $C'$ is reachable from $C$ and hence from $x$ before $x$ finishes). Hence $x$, and therefore some vertex of $C$, finishes after every vertex of $C'$: $f(C) > f(C')$.
• Case 2: $x \in C'$. Then since there is no edge from $C'$ back into $C$ (acyclicity of $G^{SCC}$ again), DFS from $x$ cannot reach any vertex of $C$. So the entire component $C'$ is discovered and finished — including the vertex achieving $f(C')$ — strictly before DFS ever discovers any vertex of $C$ (because $x$ was the first vertex found in $C \cup C'$, so $C$ vertices are still white when $C'$ finishes). Hence every vertex of $C$ finishes later, giving $f(C) > f(C')$ again.

In both cases $f(C) > f(C')$, proving the lemma. $\blacksquare$ Consequence. This lemma says that if we rank the SCCs by their maximum finish time $f(C)$ from a DFS of $G$, that ranking is exactly a reverse topological order of $G^{SCC}$ — every edge $C \to C'$ has $f(C) > f(C')$, so the component with globally largest finish time is a source of $G^{SCC}$ (nothing points into it from another component, since anything pointing in would have to finish even later). Why the second pass then works. In Phase 3 we run DFS on $G^T$, and $G^{SCC^T}$ (the component graph of the transpose) is exactly $G^{SCC}$ with every edge reversed. So the component with the largest $f(C)$-value — a source in $G^{SCC}$ — becomes a sink in $G^{SCC^T}$: no edges leave it in the transposed component graph. We start Phase 3 at a vertex of that component (it sits on top of the finish stack). Since it is a sink in $G^{SCC^T}$, DFS from it in $G^T$ cannot escape to any other component — the search explores exactly the vertices of that one SCC (they are mutually reachable within the component, and reachability confirms it can't leak out). So the first DFS tree grown in Phase 3 is exactly that one SCC. Now remove that finished component and repeat the argument inductively: among the remaining unvisited components, whichever has the next-highest $f(C)$ value is a source in the remaining subgraph of $G^{SCC}$, hence a sink in the remaining subgraph of $G^{SCC^T}$, and it sits highest on the still-unpopped part of the stack. So Phase 3's next DFS tree, rooted there, again cannot escape its own component. By induction, every DFS tree produced in Phase 3 is exactly one SCC, and every vertex is assigned to exactly one tree (since Phase 3 is a complete DFS forest over all vertices of $G^T$). This proves Kosaraju's algorithm partitions $V$ correctly into SCCs. $\blacksquare$

Tradeoffs. Kosaraju's algorithm is conceptually the simplest linear-time SCC algorithm to prove correct, because the proof reduces to one clean lemma about finish times and component-DAG structure. Its practical downside is needing to materialize $G^T$ explicitly and store two full adjacency structures, and needing two full DFS passes with an intervening full graph traversal to sort by finish time. Tarjan's single-pass algorithm and the path-based Gabow algorithm achieve the same $O(V+E)$ bound with one DFS pass and no explicit transpose, at the cost of a more intricate low-link invariant that is harder to prove correct from first principles — Kosaraju's algorithm is usually taught first precisely because its proof is so self-contained.

Take the graph from the diagram above with vertices $\{A,B,C,D,E,F,G\}$ and edges:

Phase 1 — DFS on $G$, starting at $A$ (assume adjacency lists list neighbors alphabetically):

Stack from bottom to top: $F, E, G, D, C, B, A$. Popping gives the order $A, B, C, D, G, E, F$.

Phase 2 — Transpose. Reversing every edge gives $G^T$: $B\!\to\!A,\ C\!\to\!B,\ A\!\to\!C,\ D\!\to\!C,\ E\!\to\!D,\ F\!\to\!E,\ D\!\to\!F,\ G\!\to\!D$.

Phase 3 — DFS on $G^T$ in the order $A, B, C, D, G, E, F$ (popped from the stack):

Output: three SCCs, $\{A,B,C\}$, $\{D,E,F\}$, $\{G\}$ — matching the diagram exactly, and matching the ground truth since $A,B,C$ form a 3-cycle, $D,E,F$ form a 3-cycle, and $G$ has no outgoing or return path. Notice the crucial detail: even though $D \to G$ is an edge in $G$, when Phase 3 reaches the popped vertex $D$ and explores $G^T$, the edge in $G^T$ is $G \to D$, not $D \to G$ — so DFS from $D$ never reaches $G$, correctly keeping $G$ isolated as its own SCC, and confirming the component graph really is the acyclic chain $\{A,B,C\} \to \{D,E,F\} \to \{G\}$.

Kosaraju's algorithm is named for S. Rao Kosaraju, who described the two-pass DFS-on-transpose technique in an unpublished 1978 note; the same idea was independently rediscovered and popularized by Micha Sharir in 1981, and it is sometimes called the Kosaraju–Sharir algorithm. The technique sits alongside Robert Tarjan's 1972 single-pass low-link algorithm as one of the two classic linear-time methods for SCC decomposition, both building directly on the DFS discovery/finish-time framework that Tarjan himself had systematized for reasoning about graph structure.

Compilers and build systems use SCC decomposition to find groups of mutually recursive functions or circular module dependencies before doing dependency-ordered compilation; each SCC in the call graph must be compiled or type-checked as a unit, and the acyclic component graph then gives a valid compilation order via Topological Sort. Package managers and dependency resolvers (in language ecosystems and container-build tools) use the same idea to detect cyclic dependencies that must be flagged to the user rather than silently ordered. Deadlock detection in operating systems and database systems models resource-allocation graphs as directed graphs, where a cycle among "waiting-for" edges signals a deadlock; SCC computation finds all such cycles simultaneously rather than searching for one cycle at a time. Web-scale graph analysis (search-engine crawling, citation-network research, social-network community structure) uses SCC decomposition to identify the "core" of mutually-linking pages versus pages that are only ever linked to or only ever link out, a structure famously described in large-scale studies of the web graph's "bowtie" shape. Model checking and static analysis tools that build control-flow or state-transition graphs use SCCs to isolate loops and recursive structures for separate fixpoint or termination analysis.

Ask the tutor: How does Tarjan's single-pass low-link algorithm find the same SCCs without ever building the transpose graph?