--- title: Topological Sort and Strong Connectivity module: Graphs moduleNumber: 6 lessonNumber: 3 order: 603 summary: | Directed acyclic graphs model dependencies: tasks that must precede other tasks. A _topological order_ lays such a graph out in a line so every edge points forward, and depth-first finish times yield one almost for free. We then ask the harder question for graphs _with_ cycles: which vertices can reach each other? The answer is the strongly connected components, found by a two-pass DFS. topics: [Graph Traversal] sources: - book: CLRS ref: "Ch. 22 — Elementary Graph Algorithms" - book: Skiena ref: "§5 — Graph Traversal" - book: Erickson ref: "Ch. 6 — Depth-First Search" practice: - title: 'Course Schedule' slug: course-schedule difficulty: Medium - title: 'Course Schedule II' slug: course-schedule-ii difficulty: Medium - title: 'Find Eventual Safe States' slug: find-eventual-safe-states difficulty: Medium - title: 'Alien Dictionary' slug: alien-dictionary difficulty: Hard - title: 'Critical Connections in a Network' slug: critical-connections-in-a-network difficulty: Hard --- Many problems are really questions about _order_. To compile a program you must build each module before the ones that depend on it; to follow a recipe you must chop before you sauté; to finish a degree you must clear the prerequisites of each course. Each of these is a **directed acyclic graph**, a digraph with no directed cycles, and the task of "find a consistent order" is **topological sorting**. [Depth-first search](/algorithms/graphs/representations-and-traversal), with its finish-time timestamps from the previous lesson, solves it almost incidentally. ## Directed acyclic graphs > **Definition (Directed acyclic graph).** A directed acyclic graph (DAG) is a directed graph that contains no > directed cycle. The absence of cycles is what makes a consistent ordering possible: if task $a$ must precede $b$ and $b$ must precede $a$, no linear order can satisfy both. Here is a small DAG of course prerequisites, where an edge $u \to v$ means "$u$ must come before $v$": $$ % caption: A small DAG of course prerequisites where an edge $u$ to $v$ means $u$ precedes % $v$. \begin{tikzpicture}[every node/.style={circle, draw, minimum size=8mm, font=\small}, node distance=16mm] \node (a) {$a$}; \node (b) [right=of a] {$b$}; \node (c) [right=of b] {$c$}; \node (d) [below=12mm of a] {$d$}; \node (e) [right=of d] {$e$}; \draw[->, >=Stealth] (a) -- (b); \draw[->, >=Stealth] (b) -- (c); \draw[->, >=Stealth] (a) -- (d); \draw[->, >=Stealth] (d) -- (e); \draw[->, >=Stealth] (e) -- (c); \draw[->, >=Stealth] (b) -- (e); \end{tikzpicture} $$ ## Topological order > **Definition (Topological order).** A topological order of a DAG $G = (V, E)$ is a linear ordering of its > vertices such that for every edge $(u, v)$, vertex $u$ appears before $v$. Picture all the vertices pinned along a horizontal line so that _every_ edge points rightward. The DAG above admits the order $a, b, d, e, c$; each of its six edges goes left to right: $$ % caption: The DAG laid out in topological order $a, b, d, e, c$ with every edge pointing % rightward. \begin{tikzpicture}[every node/.style={circle, draw, minimum size=8mm, font=\small}, node distance=14mm] \node (a) {$a$}; \node (b) [right=of a] {$b$}; \node (d) [right=of b] {$d$}; \node (e) [right=of d] {$e$}; \node (c) [right=of e] {$c$}; \draw[->, >=Stealth] (a) to[bend left=30] (b); \draw[->, >=Stealth] (a) to[bend right=30] (d); \draw[->, >=Stealth] (b) to[bend left=30] (e); \draw[->, >=Stealth] (d) to[bend right=30] (e); \draw[->, >=Stealth] (e) to[bend left=30] (c); \draw[->, >=Stealth] (b) to[bend left=42] (c); \end{tikzpicture} $$ Topological orders are usually _not_ unique; $a, d, b, e, c$ works equally well. Two facts tie ordering to acyclicity: > **Theorem.** A directed graph has a topological order if and only if it is acyclic. > **Proof.** The forward direction is immediate: a directed cycle could never be > laid out with all edges pointing the same way. The converse, that every DAG > _has_ such an order, is what the algorithm below constructs. $\qed$ ## Topological sort via DFS finish times All three texts draw out the same observation, linking acyclicity to depth-first search's edge classification from the previous lesson:[^erickson-back] > **Lemma.** A directed graph is acyclic if and only if a depth-first search of > it produces **no back edges**. > **Proof.** A back edge $(u, v)$ runs from $u$ to a gray ancestor $v$; the tree > path from $v$ down to $u$ together with that edge forms a cycle. Conversely, in > any cycle the first vertex discovered becomes a gray ancestor of the others, so > the edge closing the cycle is a back edge. $\qed$ Since DAGs have no back edges, every edge of a DAG is a tree, forward, or cross edge, and for all three of those, the finish times obey $u.f > v.f$. That single inequality gives the algorithm: > **Theorem.** In a DAG, for every edge $(u, v)$ we have $u.f > v.f$. Hence > listing vertices in order of _decreasing finish time_ yields a topological > order. So we run DFS, and as each vertex finishes we push it onto the front of a list. When DFS completes, the list reads off a valid topological order.[^clrs-topo] ```algorithm caption: $\textsc{Topological-Sort}(G)$ — order a DAG by DFS finish times number: 1 $L \gets$ empty linked list foreach vertex $u \in V$ do $u.color \gets \text{white}$ foreach vertex $u \in V$ do if $u.color = \text{white}$ then call $\textsc{TS-Visit}(G, u, L)$ return $L$ ``` ```algorithm caption: $\textsc{TS-Visit}(G, u, L)$ — finish $u$, then prepend it to $L$ number: 2 $u.color \gets \text{gray}$ foreach $v$ adjacent to $u$ do if $v.color = \text{white}$ then call $\textsc{TS-Visit}(G, v, L)$ $u.color \gets \text{black}$ prepend $u$ to the front of $L$ // smaller finish goes later ``` > **Correctness.** Consider any edge $(u, v)$. When DFS explores it, $v$ is white, > gray, or black. It cannot be gray — that would be a back edge, impossible in a > DAG. If $v$ is white, it becomes a descendant of $u$ and finishes first, so > $u.f > v.f$. If $v$ is black, it already finished, so again $u.f > v.f$. In > every case $u$ finishes after $v$, so prepending on finish places $u$ before > $v$ in $L$, the defining property of a topological order. $\qed$ **Running time.** This is just DFS plus $O(1)$ work per vertex to splice it into the list, so it runs in $\Theta(V + E)$, which is [linear](/algorithms/foundations/asymptotic-analysis). ::impl{algo="topological_sort"} ### A full trace on the prerequisite DAG Run the algorithm on the prerequisite DAG, starting at $a$ and taking $a$'s adjacency list in the order $d, b$ (adjacency-list order is arbitrary; this one keeps the trace short). Every discovery and finish ticks the same clock, so the run is a sequence of ten timestamped events: | time | event | call stack | $L$ afterwards | | ---- | ------------ | --------------- | ---------------------------------- | | 1 | discover $a$ | $a$ | $\langle\,\rangle$ | | 2 | discover $d$ | $a, d$ | $\langle\,\rangle$ | | 3 | discover $e$ | $a, d, e$ | $\langle\,\rangle$ | | 4 | discover $c$ | $a, d, e, c$ | $\langle\,\rangle$ | | 5 | finish $c$ | $a, d, e$ | $\langle c \rangle$ | | 6 | finish $e$ | $a, d$ | $\langle e, c \rangle$ | | 7 | finish $d$ | $a$ | $\langle d, e, c \rangle$ | | 8 | discover $b$ | $a, b$ | $\langle d, e, c \rangle$ | | 9 | finish $b$ | $a$ | $\langle b, d, e, c \rangle$ | | 10 | finish $a$ | — | $\langle a, b, d, e, c \rangle$ | At time 8, $b$ inspects its neighbors $c$ and $e$, finds both black (finished), and finishes immediately — those two edges become _cross edges_, and the inequality $b.f > c.f$, $b.f > e.f$ holds for them just as it does for tree edges. The final list $\langle a, b, d, e, c \rangle$ is the topological order, and sorting the vertices by decreasing $f$ reproduces it exactly. Every edge, drawn below the sorted line, points rightward: $$ % caption: DFS finish times on the DAG (top); sorting by decreasing $f$ gives the % topological order $a, b, d, e, c$ with all edges forward (bottom). \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=8mm, font=\small}] \definecolor{acc}{HTML}{2348F2} % --- DAG with finish times --- \node[V] (a) at (0,1.4) {$a$}; \node[V] (b) at (1.5,1.4) {$b$}; \node[V] (c) at (3.0,1.4) {$c$}; \node[V] (d) at (0,0) {$d$}; \node[V] (e) at (1.5,0) {$e$}; \draw[->] (a) -- (b); \draw[->] (b) -- (c); \draw[->] (a) -- (d); \draw[->] (d) -- (e); \draw[->] (e) -- (c); \draw[->] (b) -- (e); \node[font=\scriptsize, acc] at (0,2.1) {$f{=}10$}; \node[font=\scriptsize, acc] at (1.5,2.1) {$f{=}9$}; \node[font=\scriptsize, acc] at (3.0,2.1) {$f{=}5$}; \node[font=\scriptsize, acc] at (-0.85,-0.05) {$f{=}7$}; \node[font=\scriptsize, acc] at (1.5,-0.75) {$f{=}6$}; % --- divider + sorted line, pushed well below the DAG --- \node[font=\footnotesize] at (1.7,-1.75) {sorted by decreasing f\/inish time}; \begin{scope}[yshift=-38mm] \foreach \v/\f/\x in {a/10/0, b/9/1.2, d/7/2.4, e/6/3.6, c/5/4.8} { \node[V, fill=acc!12] (\v 2) at (\x,0) {$\v$}; \node[font=\scriptsize, black] at (\x,-0.85) {$\f$}; } % forward edges arced ABOVE — they nest without crossing (no interleaving pair on this side) \draw[->] (a2) to[bend left=24] (b2); \draw[->] (e2) to[bend left=24] (c2); \draw[->] (b2) to[bend left=50] (e2); % skips d: arc high enough to clear it \draw[->] (b2) to[bend left=64] (c2); % skips d and e: highest arc % the two interleaving edges go BELOW so they never cross the above arcs \draw[->] (a2) to[bend right=52] (d2); % skips b \draw[->] (d2) to[bend right=22] (e2); \end{scope} \end{tikzpicture} $$ ### Why a topological order matters: the evaluation DAG For example, take computing Fibonacci numbers $F_n = F_{n-1} + F_{n-2}$. The naive recursion $\textsc{Fibo}(n)$ branches into $\textsc{Fibo}(n-1)$ and $\textsc{Fibo}(n-2)$, and its call tree is exponential, but _most of its nodes are duplicates_. If we collapse the identical subproblems into single nodes, the recursion tree becomes a small **DAG**: one node per value $F_i$, with an edge $F_i \to F_j$ whenever computing $F_i$ needs $F_j$. $$ % caption: The Fibonacci evaluation DAG with one node per value and an edge to each needed % subproblem. \begin{tikzpicture}[every node/.style={circle, draw, minimum size=9mm, font=\small}, node distance=13mm] \node (f5) {$F_5$}; \node (f4) [right=of f5] {$F_4$}; \node (f3) [right=of f4] {$F_3$}; \node (f2) [right=of f3] {$F_2$}; \node (f1) [right=of f2] {$F_1$}; \node (f0) [right=of f1] {$F_0$}; \draw[->, >=Stealth] (f5) to[bend left=30] (f4); \draw[->, >=Stealth] (f5) to[bend right=34] (f3); \draw[->, >=Stealth] (f4) to[bend left=30] (f3); \draw[->, >=Stealth] (f4) to[bend right=34] (f2); \draw[->, >=Stealth] (f3) to[bend left=30] (f2); \draw[->, >=Stealth] (f3) to[bend right=34] (f1); \draw[->, >=Stealth] (f2) to[bend left=30] (f1); \draw[->, >=Stealth] (f2) to[bend right=34] (f0); \end{tikzpicture} $$ To compute $F_n$ we must evaluate every node _after_ the nodes it points to are already known, that is, **in a valid topological order of the evaluation DAG**. Here the order is read off by level: $F_0, F_1, F_2, \dots, F_n$. Filling an array in that order computes each value with $O(1)$ work, turning exponential recursion into a single linear sweep: ```algorithm caption: $\textsc{Dyn-Fibo}(n)$ — evaluate the DAG in topological order number: 3 allocate array $F[0 \mathbin{..} n]$ $F[0] \gets 0$; $F[1] \gets 1$ for $i \gets 2$ to $n$ do $F[i] \gets F[i-1] + F[i-2]$ // predecessors already done return $F[n]$ ``` The lesson generalizes: whenever quantities depend on one another acyclically, their dependency digraph is a DAG, and a topological order gives a safe order in which to evaluate them, predecessors first. This is the structure underlying dynamic programming, which we return to later. ### Kahn's algorithm: peeling sources Skiena presents the equivalent _Kahn's algorithm_, which never mentions finish times.[^skiena-scc] The idea is an induction on sources. A DAG always has at least one vertex of in-degree $0$ (follow edges backward from any vertex; with no cycle the walk must stop, and it stops at a source). Any source can safely go first in the order, and deleting it leaves a smaller DAG, so repeat. ```algorithm caption: $\textsc{Kahn-Topological-Sort}(G)$ — repeatedly emit a source number: 4 compute $indeg[v]$ for every $v \in V$ // one pass over all adjacency lists $Q \gets$ queue of all vertices with $indeg[v] = 0$ $L \gets$ empty list while $Q$ is nonempty do $u \gets$ dequeue $Q$; append $u$ to $L$ foreach $v$ adjacent to $u$ do $indeg[v] \gets indeg[v] - 1$ // delete $u$'s out-edges if $indeg[v] = 0$ then enqueue $v$ if $|L| < |V|$ then report "cycle" else return $L$ ``` The deletion is virtual: decrementing $indeg[v]$ stands in for removing the edge $(u,v)$. On the prerequisite DAG the in-degrees start at $a{:}\,0$, $b{:}\,1$, $c{:}\,2$, $d{:}\,1$, $e{:}\,2$, and the run proceeds (breaking queue ties alphabetically): | step | emit | decrements | in-degrees left ($b, c, d, e$) | queue after | | ---- | ---- | ------------------------ | ------------------------------ | ----------- | | 1 | $a$ | $b \to 0$, $d \to 0$ | $0, 2, 0, 2$ | $b, d$ | | 2 | $b$ | $c \to 1$, $e \to 1$ | $-, 1, 0, 1$ | $d$ | | 3 | $d$ | $e \to 0$ | $-, 1, -, 0$ | $e$ | | 4 | $e$ | $c \to 0$ | $-, 0, -, -$ | $c$ | | 5 | $c$ | — | done | empty | The result, $a, b, d, e, c$, happens to match the DFS order; with a different tie-break ($d$ before $b$ at step 1) it would produce the equally valid $a, d, b, e, c$. Two properties fall out of the loop structure: - **Cycle detection is free.** If the queue empties while vertices remain, every leftover vertex has in-degree $\ge 1$ among the leftovers, and following in-edges backward inside that set forever must revisit a vertex: the leftovers contain a cycle. So $|L| < |V|$ if and only if $G$ is not a DAG — Kahn's algorithm doubles as a cycle detector. - **Counting the orders.** Whenever the queue holds $k$ vertices, any of the $k$ may go next; the algorithm enumerates one topological order per tie-break policy, and swapping the queue for a priority queue produces the lexicographically smallest order at $O(E + V \log V)$ cost. **Running time.** Computing all in-degrees touches every edge once, $\Theta(V+E)$. Each vertex is enqueued and dequeued at most once ($\Theta(V)$), and each edge $(u,v)$ triggers exactly one decrement, when $u$ is emitted ($\Theta(E)$). Total: $\Theta(V + E)$, matching the DFS method. ::impl{algo="kahn_topological_sort"} $$ % caption: Kahn's algorithm on the prerequisite DAG: each vertex tagged with its % in-degree; repeatedly emit an in-degree-$0$ vertex, yielding the order % $\langle a, b, d, e, c \rangle$. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=9mm, font=\small}] \definecolor{acc}{HTML}{2348F2} \node[V, fill=acc!20] (a) {$a$}; \node[V] (b) [right=16mm of a] {$b$}; \node[V] (c) [right=16mm of b] {$c$}; \node[V] (d) [below=14mm of a] {$d$}; \node[V] (e) [right=16mm of d] {$e$}; \draw[->] (a) -- (b); \draw[->] (b) -- (c); \draw[->] (a) -- (d); \draw[->] (d) -- (e); \draw[->] (e) -- (c); \draw[->] (b) -- (e); \node[font=\scriptsize, acc] at ($(a)+(0,0.85)$) {in-deg $0$}; \node[font=\scriptsize] at ($(b)+(0,0.85)$) {$1$}; \node[font=\scriptsize] at ($(c)+(0,0.85)$) {$2$}; \node[font=\scriptsize] at ($(d)+(-0.95,0)$) {$1$}; \node[font=\scriptsize] at ($(e)+(0,-0.85)$) {$2$}; \node[font=\footnotesize] at (0.0,-3.7) {emit order:}; \foreach \v/\x in {a/1.6, b/2.3, d/3.0, e/3.7, c/4.4} \node[draw, minimum size=5mm, fill=acc!12, font=\scriptsize] at (\x,-3.7) {$\v$}; \end{tikzpicture} $$ ## Strong connectivity DAGs are the cycle-free case. What can we say about a _general_ digraph, cycles and all? The right notion of "connected" for directed graphs is mutual reachability. > **Definition (Strongly connected component).** Two vertices $u$ and $v$ are **strongly connected** if there is a directed > path from $u$ to $v$ _and_ one from $v$ to $u$. A strongly connected > component (SCC) is a maximal set of mutually-reachable vertices. Strong connectivity partitions $V$ into SCCs. Collapsing each component to a single super-vertex yields the **component graph** (or _condensation_), and the following holds: > **Lemma.** The component graph of any digraph is always a DAG. > **Proof.** If it had a cycle, the components on that cycle could all reach one > another and would have been merged into one larger component, contradicting > maximality. $\qed$ So every directed graph is, at the coarse level of its components, a DAG. SCCs are the standard first step in analyzing a digraph: find the components, contract them, and reason about the resulting DAG. $$ % caption: A digraph with two strongly connected components $a,b$ and $c,d$ linked by % edges from $a,b$ to $c,d$. \begin{tikzpicture}[every node/.style={circle, draw, minimum size=8mm, font=\small}, node distance=15mm] \node (a) {$a$}; \node (b) [right=of a] {$b$}; \node (c) [below=12mm of a] {$c$}; \node (d) [below=12mm of b] {$d$}; \draw[->, >=Stealth] (a) to[bend left=20] (b); \draw[->, >=Stealth] (b) to[bend left=20] (a); \draw[->, >=Stealth] (b) -- (d); \draw[->, >=Stealth] (c) to[bend left=20] (d); \draw[->, >=Stealth] (d) to[bend left=20] (c); \draw[->, >=Stealth] (a) -- (c); \end{tikzpicture} $$ Here $\set{a, b}$ form one SCC (each reaches the other) and $\set{c, d}$ another, and the only edges between the two groups run from $\set{a,b}$ to $\set{c,d}$. Collapsing each component to a super-vertex leaves the two-node condensation, itself a DAG, with its own trivial topological order $\set{a,b}$ then $\set{c,d}$: $$ % caption: The two-node condensation DAG with component $a,b$ pointing to component $c,d$. \begin{tikzpicture}[every node/.style={draw, minimum size=9mm, inner xsep=3mm, font=\small}, node distance=20mm] \node (ab) {$a$, $b$}; \node (cd) [right=of ab] {$c$, $d$}; \draw[->, >=Stealth] (ab) -- (cd); \end{tikzpicture} $$ ### Kosaraju's two-pass algorithm The cleanest way to find SCCs, due to Kosaraju and Sharir, is two depth-first searches with a transpose in between.[^skiena-scc] The **transpose** $G^{\mathsf{T}}$ is $G$ with every edge reversed. It has _exactly the same SCCs_ as $G$: a round trip $u \to v \to u$ in $G$ becomes the round trip $u \to v \to u$ in $G^{\mathsf{T}}$ traversed the other way, so mutual reachability is untouched. ```algorithm caption: $\textsc{Strongly-Connected-Components}(G)$ — Kosaraju's two passes number: 5 call $\textsc{DFS}(G)$ to compute the finish time $u.f$ for each vertex $u$ compute $G^{\mathsf{T}}$ // reverse all edges call $\textsc{DFS}(G^{\mathsf{T}})$, considering vertices in order of decreasing $u.f$ output the vertices of each tree in the second forest as one SCC ``` **Why it works (the intuition).** Imagine the component graph laid out in topological order, sources on the left. The _first_ DFS on $G$ assigns the largest finish time to a vertex in a _source_ component of that DAG. When we then run DFS on $G^{\mathsf{T}}$, where every component-graph edge is reversed, and start from that highest-finishing vertex, we are launching from a _sink_ of the reversed component graph. From a sink, the search cannot leak into any other component, so it visits _exactly_ one SCC and stops. Peeling components off in decreasing finish order keeps this true at every step. The whole procedure is two DFS passes plus a transpose, all linear, so SCCs cost $\Theta(V + E)$. The picture below shows the source/sink reversal. The first DFS on a graph with three SCCs lands the largest finish time ($12$) inside the **source** component $\set{a, b}$; reversing the edges turns that source into a sink, so the second DFS, launched from $a$, is trapped inside one SCC and peels it off cleanly: $$ % caption: Kosaraju's idea: the source SCC of $G$ holds the highest finish time, so the % second DFS on $G^{\mathsf{T}}$ launches from a sink and peels one SCC at a % time. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=7mm, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[font=\footnotesize] at (2.6,2.5) {\textbf{$G$ with DFS f\/inish times $f$}}; \draw[dashed, draw=acc] (-0.6,0.5) rectangle (1.8,2.0); \draw[dashed, draw=acc] (2.0,0.5) rectangle (4.4,2.0); \draw[dashed, draw=acc] (4.6,0.5) rectangle (6.0,2.0); \node[V] (a) at (0,1.4) {$a$}; \node[V] (b) at (1.2,1.4) {$b$}; \node[V] (c) at (2.6,1.4) {$c$}; \node[V] (d) at (3.8,1.4) {$d$}; \node[V] (e) at (5.3,1.4) {$e$}; \draw[->] (a) to[bend left=25] (b); \draw[->] (b) to[bend left=25] (a); \draw[->] (c) to[bend left=25] (d); \draw[->] (d) to[bend left=25] (c); \draw[->, acc, thick] (b) -- (c); \draw[->, acc, thick] (d) -- (e); \node[font=\scriptsize] at (0,0.75) {$f{=}12$}; \node[font=\scriptsize] at (1.2,0.75) {$11$}; \node[font=\scriptsize] at (2.6,0.75) {$8$}; \node[font=\scriptsize] at (3.8,0.75) {$9$}; \node[font=\scriptsize] at (5.3,0.75) {$5$}; \node[font=\footnotesize] at (2.6,-1.0) {\textbf{condensation}}; \node[draw, fill=acc!15, inner xsep=2.5mm] (C1) at (0.6,-1.9) {$a$, $b$}; \node[draw, inner xsep=2.5mm] (C2) at (2.8,-1.9) {$c$, $d$}; \node[draw, inner xsep=2.5mm] (C3) at (5.0,-1.9) {$e$}; \draw[->, thick] (C1) -- (C2); \draw[->, thick] (C2) -- (C3); \node[font=\scriptsize, acc] at (0.6,-2.7) {source: $f_{\max}=12$}; \node[font=\scriptsize] at (5.0,-2.7) {sink}; \end{tikzpicture} $$ The intuition hardens into two short proofs. Write $f(C) = \max_{u \in C} u.f$ for the largest first-pass finish time inside component $C$. > **Lemma (components order by finish time).** If $G$ has an edge from component > $C$ to a different component $C'$, then $f(C) > f(C')$. > **Proof.** Let $x$ be the first vertex of $C \cup C'$ that the first DFS > discovers. If $x \in C$: at that moment every vertex of $C \cup C'$ is still > white and reachable from $x$ (within $C$, then across the $C \to C'$ edge, > then within $C'$), so all of them become descendants of $x$ and finish before > $x$ does. Hence $f(C) = x.f > f(C')$. If instead $x \in C'$: no path leads > from $C'$ back to $C$ (one would merge the two components), so no vertex of > $C$ is touched while $x$ is on the stack. All of $C'$ descends from $x$ and > finishes before $x.f$, while every vertex of $C$ is discovered only after $x$ > finishes. Again $f(C) > x.f \ge f(C')$. $\qed$ The lemma says the first pass computes, for free, a reverse topological order of the condensation: listing components by decreasing $f(C)$ lists them source to sink. The second pass exploits it. > **Theorem (Kosaraju correctness).** Each tree of the second DFS spans exactly > one SCC of $G$. > **Proof.** Induct on the trees in the order the second pass grows them. > Suppose every earlier tree spanned a whole component, and let $r$ be the next > root: the unvisited vertex with the largest finish time, living in component > $C$. The search from $r$ in $G^{\mathsf{T}}$ reaches all of $C$, since an SCC > is strongly connected in both directions and no vertex of $C$ was visited > earlier (earlier trees are whole components other than $C$). It reaches > nothing else: an edge of $G^{\mathsf{T}}$ leaving $C$ points to a component > $C''$ that has an edge _into_ $C$ in $G$, so the lemma gives > $f(C'') > f(C) \ge r.f$. The vertex realizing $f(C'')$ finished later than > every unvisited vertex, so it was already consumed by an earlier tree, and by > induction all of $C''$ went with it. The search from $r$ therefore stops at > the border of $C$, spanning exactly $C$. $\qed$ ### A complete run Here is the full machinery on an eight-vertex digraph adapted from CLRS's worked example.[^clrs-topo] Its components are $C_1 = \{a, b, e\}$, $C_2 = \{c, d\}$, $C_3 = \{f, g\}$, and $C_4 = \{h\}$. **Pass 1** runs DFS on $G$ from $a$ with alphabetical adjacency lists and records finish times: $a$ starts a tree at time $1$ and the exploration order is $a, b, c, d, h, g, f, e$, giving the finish times shown below. $$ % caption: Pass 1 on $G$: DFS finish times $f$, with the four SCCs boxed. The % largest $f$ in each component decreases along the condensation: % $16 > 12 > 11 > 6$. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small}] \definecolor{acc}{HTML}{2348F2} \draw[dashed, draw=acc] (-0.65,-0.95) rectangle (2.35,2.5); \draw[dashed, draw=acc] (2.75,1.05) rectangle (5.65,2.5); \draw[dashed, draw=acc] (2.45,-0.95) rectangle (5.25,0.75); \draw[dashed, draw=acc] (5.75,0.05) rectangle (6.95,1.55); \node[V] (a) at (0,1.7) {$a$}; \node[V] (b) at (1.7,1.7) {$b$}; \node[V] (c) at (3.4,1.7) {$c$}; \node[V] (d) at (5.0,1.7) {$d$}; \node[V] (e) at (0.85,0) {$e$}; \node[V] (f) at (3.0,0) {$f$}; \node[V] (g) at (4.6,0) {$g$}; \node[V] (h) at (6.3,0.85) {$h$}; \draw[->] (a) -- (b); \draw[->] (b) -- (c); \draw[->] (b) -- (e); \draw[->] (b) -- (f); \draw[->] (c) to[bend left=18] (d); \draw[->] (d) to[bend left=18] (c); \draw[->] (c) -- (g); \draw[->] (d) -- (h); \draw[->] (e) -- (a); \draw[->] (e) -- (f); \draw[->] (f) to[bend left=22] (g); \draw[->] (g) to[bend left=22] (f); \draw[->] (g) -- (h); \node[font=\scriptsize, acc] at (0,2.25) {$f{=}16$}; \node[font=\scriptsize, acc] at (1.7,2.25) {$15$}; \node[font=\scriptsize, acc] at (3.15,2.25) {$12$}; \node[font=\scriptsize, acc] at (5.3,2.25) {$7$}; \node[font=\scriptsize, acc] at (0.85,-0.6) {$14$}; \node[font=\scriptsize, acc] at (2.75,-0.6) {$10$}; \node[font=\scriptsize, acc] at (4.85,-0.6) {$11$}; \node[font=\scriptsize, acc] at (6.3,0.28) {$6$}; \end{tikzpicture} $$ Reading the vertices by decreasing finish time gives the processing order for pass 2: $$ a\,(16),\ b\,(15),\ e\,(14),\ c\,(12),\ g\,(11),\ f\,(10),\ d\,(7),\ h\,(6). $$ **Pass 2** reverses every edge and launches DFS roots in that order. Each root grows a tree, and each tree is one SCC: | root | reason it starts a tree | tree grown in $G^{\mathsf{T}}$ | SCC found | | ---- | ---------------------------------- | --------------------------------------- | -------------- | | $a$ | largest $f$ overall | $a \to e$, $e \to b$ | $\{a, b, e\}$ | | $c$ | largest $f$ still unvisited ($12$) | $c \to d$ | $\{c, d\}$ | | $g$ | next unvisited ($11$) | $g \to f$ | $\{f, g\}$ | | $h$ | next unvisited ($6$) | (no unvisited neighbor) | $\{h\}$ | Each tree halts at the border of its own component. Every reversed edge that leaves a tree — $c \to b$ from the second, $f \to b$ and $f \to e$ from the third, $h \to d$ and $h \to g$ from the last — lands on an already-visited vertex, because it exits toward a component with larger $f(C)$, which the decreasing-$f$ schedule has already peeled. The first tree needs no such luck: a source component has no incoming edges in $G$, hence no outgoing edges in $G^{\mathsf{T}}$, so the search from $a$ is walled in from the start: $$ % caption: Pass 2 on $G^{\mathsf{T}}$ (all edges reversed): roots taken by % decreasing $f$ grow the four trees (thick blue tree edges); every % other reversed edge leads to an already-visited component. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small}] \definecolor{acc}{HTML}{2348F2} \node[V, fill=acc!12] (a) at (0,1.7) {$a$}; \node[V, fill=acc!12] (b) at (1.7,1.7) {$b$}; \node[V, fill=acc!12] (c) at (3.4,1.7) {$c$}; \node[V, fill=acc!12] (d) at (5.0,1.7) {$d$}; \node[V, fill=acc!12] (e) at (0.85,0) {$e$}; \node[V, fill=acc!12] (f) at (3.0,0) {$f$}; \node[V, fill=acc!12] (g) at (4.6,0) {$g$}; \node[V, fill=acc!12] (h) at (6.3,0.85) {$h$}; \draw[->, black] (b) -- (a); \draw[->, black] (c) -- (b); \draw[->, acc, very thick] (e) -- (b); \draw[->, black] (f) -- (b); \draw[->, acc, very thick] (c) to[bend left=18] (d); \draw[->, black] (d) to[bend left=18] (c); \draw[->, black] (g) -- (c); \draw[->, black] (h) -- (d); \draw[->, acc, very thick] (a) -- (e); \draw[->, black] (f) -- (e); \draw[->, acc, very thick] (g) to[bend left=22] (f); \draw[->, black] (f) to[bend left=22] (g); \draw[->, black] (h) -- (g); \node[font=\scriptsize, acc] at (0,2.25) {tree 1}; \node[font=\scriptsize, acc] at (3.4,2.25) {tree 2}; \node[font=\scriptsize, acc] at (4.85,-0.6) {tree 3}; \node[font=\scriptsize, acc] at (6.3,0.28) {tree 4}; \end{tikzpicture} $$ Contracting the four components produces the condensation, and the maxima $f(C_1) = 16 > f(C_2) = 12 > f(C_3) = 11 > f(C_4) = 6$ read off a topological order of it, as the lemma guarantees: $$ % caption: The condensation of the eight-vertex digraph. Decreasing component % maxima $f(C)$ — $16, 12, 11, 6$ — give its topological order. \begin{tikzpicture}[>=Stealth, font=\small, C/.style={draw, inner xsep=2.5mm, inner ysep=1.8mm, font=\small}] \definecolor{acc}{HTML}{2348F2} \node[C, fill=acc!12] (abe) at (0,0.8) {$a$, $b$, $e$}; \node[C] (cd) at (3.0,1.7) {$c$, $d$}; \node[C] (fg) at (3.0,0) {$f$, $g$}; \node[C] (hh) at (5.6,0.8) {$h$}; \draw[->] (abe) -- (cd); \draw[->] (abe) -- (fg); \draw[->] (cd) -- (fg); \draw[->] (cd) -- (hh); \draw[->] (fg) -- (hh); \node[font=\scriptsize, acc] at (0,0.15) {$f_{\max}=16$}; \node[font=\scriptsize, acc] at (3.0,2.35) {$f_{\max}=12$}; \node[font=\scriptsize, acc] at (3.0,-0.65) {$f_{\max}=11$}; \node[font=\scriptsize, acc] at (5.6,0.15) {$f_{\max}=6$}; \end{tikzpicture} $$ **Running time, in full.** Pass 1 is one DFS: $\Theta(V + E)$. No sorting is needed to order vertices by decreasing finish time — push each vertex onto a stack as it finishes and pop the stack in pass 2, $\Theta(V)$. Building $G^{\mathsf{T}}$ is one scan of the adjacency lists: for each $u$ and each $v \in Adj[u]$, append $u$ to $Adj^{\mathsf{T}}[v]$, which is $\Theta(V + E)$. Pass 2 is another DFS, $\Theta(V + E)$. The sum is three linear passes plus a stack: $$ \Theta(V+E) + \Theta(V) + \Theta(V+E) + \Theta(V+E) = \Theta(V + E). $$ > **Remark (Tarjan's one-pass alternative).** A single DFS can find SCCs by tracking, for > each vertex, the oldest vertex reachable via tree and back edges (its > _low-link_ value) and maintaining a stack of vertices on the current path. > When a vertex's low-link equals its own discovery time, it is the root of an > SCC, and the stack above it is popped as that component. Tarjan's method > avoids building $G^{\mathsf{T}}$ and also runs in $\Theta(V + E)$; Kosaraju's > wins on conceptual clarity. ::impl{algo="kosaraju_scc"} ## Common pitfalls - **Sorting by discovery time instead of finish time.** The two are not interchangeable. On the three-vertex DAG with edges $a \to b$, $a \to c$, $c \to b$, a DFS from $a$ that tries $b$ first discovers vertices in the order $a, b, c$ — and that order violates the edge $c \to b$. Finish times ($b$ first, then $c$, then $a$, reversed to $a, c, b$) are what the theorem guarantees. - **Appending instead of prepending.** $\textsc{TS-Visit}$ pushes each finished vertex onto the _front_ of $L$; appending to the back builds the exact reverse of a topological order. The stack formulation avoids the confusion: push on finish, then pop everything. - **Forgetting the outer loop.** Both DFS passes must restart from every still-white vertex, not just one chosen source. A DAG can have several sources, and in Kosaraju's second pass the restarts are the whole point — each restart begins a new component. - **Running toposort on a cyclic graph without checking.** DFS finish times always _produce_ an ordering, even on a cyclic input, where no valid order exists; garbage in, garbage out. Detect the cycle first: a gray-to-gray edge in DFS, or leftover vertices in Kahn's algorithm. - **Reversing the wrong thing in Kosaraju.** The second pass runs on $G^{\mathsf{T}}$ in _decreasing_ finish order of the _first_ pass. Increasing order breaks the invariant that each root's component is a source among the survivors. (The mirror-image variant — first pass on $G^{\mathsf{T}}$, second on $G$ — is fine, since $(G^{\mathsf{T}})^{\mathsf{T}} = G$.) - **Treating SCCs like undirected components.** One directed path between two vertices does not make them strongly connected; the path back must also exist. A digraph can be weakly connected (connected if you ignore directions) yet have $|V|$ singleton SCCs — any DAG is an example. ## Condensations and one-pass SCC **Tarjan's one-pass algorithm.** Kosaraju runs DFS twice; Tarjan's algorithm (1972) finds SCCs in a **single** pass.[^tarjan-scc] It carries a `low[v]` value — the smallest discovery time reachable from $v$'s subtree via at most one back or cross edge into the current stack — exactly the low-link idea reused in the [bridges and articulation points](/algorithms/graphs/bridges-and-articulation-points) lesson. Vertices are pushed onto an auxiliary stack as they are discovered; when a vertex $v$ finishes with `low[v] == disc[v]`, it is the root of an SCC, and everything above it on the stack is popped off as that component. One DFS, no transpose graph, and the components emerge in reverse topological order for free — which is why competitive-programming 2-SAT solvers almost always use Tarjan. **The condensation is the point.** Collapsing each SCC to a super-vertex yields the **condensation** $G^{\text{SCC}}$, always a DAG. Many "is there a path / can everything reach everything" questions on a general digraph reduce to a topological-order sweep over this DAG: reachability, computing the transitive closure component-wise, finding a single vertex that reaches all others (a source SCC in the condensation), or adding the fewest edges to make a digraph strongly connected (a classic result of Eswaran and Tarjan counts sources and sinks of the condensation). The two-phase pattern — find SCCs, then run a DAG algorithm on the condensation — is the template behind the whole next stretch of this module, most directly [2-SAT](/algorithms/graphs/two-sat). **Dynamic and incremental variants.** When edges arrive over time, recomputing SCCs from scratch is wasteful; incremental-SCC and incremental-topological-order algorithms (Bender, Fineman, Gilbert, Tarjan) maintain the ordering under edge insertions in near-linear total time, the machinery behind pointer-analysis and build-system dependency engines that must react to each new edge. ## Takeaways - A **DAG** is a directed graph with no cycle; it has a **topological order** (every edge points forward) **if and only if** it is acyclic. - DFS detects acyclicity by the absence of **back edges**, and listing vertices in **decreasing finish time** yields a topological order in $\Theta(V + E)$. - **Kahn's algorithm** peels off in-degree-$0$ sources with a queue, also in $\Theta(V + E)$, and detects a cycle for free: the queue runs dry with vertices left over exactly when the graph is not a DAG. - A topological order provides a **safe evaluation order** for acyclically dependent quantities, predecessors first. Collapsing the Fibonacci recursion into its **evaluation DAG** and sweeping it in topological order turns exponential recursion into a linear pass, the seed of dynamic programming. - **Strongly connected components** are maximal mutually-reachable vertex sets; contracting them always produces a **DAG**. - **Kosaraju's** two-pass DFS (run DFS, transpose, run DFS in decreasing finish order) finds all SCCs in $\Theta(V + E)$; **Tarjan's** low-link method does it in one pass. [^erickson-back]: **Erickson**, Ch. 6 — Depth-First Search — a digraph is acyclic iff DFS finds no back edge. [^clrs-topo]: **CLRS**, Ch. 22 — Elementary Graph Algorithms — topological sort by decreasing DFS finish time in $\Theta(V + E)$. [^skiena-scc]: **Skiena**, §5 — Graph Traversal — finding strongly connected components via two DFS passes. [^tarjan-scc]: **Tarjan, R. E.** (1972), "Depth-first search and linear graph algorithms," _SIAM Journal on Computing_ 1(2), 146–160 — the single-pass low-link SCC algorithm.