Topological Sort and Strongly Connected Components

Two classical applications of DFS finish times are topological sort of a directed acyclic graph (DAG) and the computation of strongly connected components (SCCs) of a directed graph. A topological order lists vertices so that every edge goes forward in the list. An SCC is a maximal set of vertices that are mutually reachable. Both of these two algorithms run in $\Theta(V+E)$ time and are standard GATE CSE graph-algorithm questions.

A topological order of a directed graph $G=(V,E)$ is a linear order of $V$ such that for every edge $u\to v$, vertex $u$ appears before $v$. Such an order exists if and only if $G$ is a DAG (equivalently: DFS finds no back edge).

Vertices $u$ and $v$ are mutually reachable when $u$ can reach $v$ and $v$ can reach $u$. Mutual reachability is an equivalence relation; its classes are the strongly connected components. The component graph (condensation) has one vertex per SCC and an edge $C_i\to C_j$ only for $C_i\ne C_j$, when some edge of $G$ goes from $C_i$ to $C_j$. The component graph is always a DAG.

Pseudocode uses adjacency lists, <- for assignment and the DFS routines of the previous note.

Equivalent view and costs. Emit vertices in decreasing finish-time order. Use adjacency lists and constant-time vertex, edge, stack and queue operations; $V$ and $E$ denote their counts in cost bounds. On a nonempty DAG the complete DFS takes $\Theta(V+E)$ time in best, average and worst cases, with $O(V)$ auxiliary marks/stack excluding the input graph and $\Theta(V)$-vertex output order. If a back edge appears, abort: no topological order exists. With the usual eager initialization of all vertex marks, a cyclic input can abort in $\Theta(V)$ best time and $\Theta(V+E)$ worst time; an average needs an input/adjacency-order distribution. The empty traversal takes $\Theta(1)$.

Related material. Repeatedly emit a vertex of indegree 0 and delete its outgoing edges. With a queue of current indegree-0 vertices the algorithm runs in $\Theta(V+E)$. If fewer than $|V|$ vertices are emitted, the graph has a cycle. Kahn's method is presented alongside the DFS method and is not a separate syllabus item. Build indegrees by a full adjacency-list pass. Under the preceding model this costs $\Theta(V+E)$ in best, average and worst cases, even if a cycle later stops the queue; auxiliary indegrees/queue use $O(V)$ words, excluding the input graph and output order. The graph need not be copied or physically deleted. Empty input costs $\Theta(1)$.

Time and space. Two complete DFS passes and one transpose take $\Theta(V+E)$ time in best, average and worst cases on nonempty adjacency-list graphs under the stated model. Reuse the recorded reverse finish order rather than comparison-sorting timestamps. Marks, finish order and recursion stacks require $O(V)$ words; an explicitly stored transpose adds $\Theta(V+E)$ words, so total auxiliary storage is $\Theta(V+E)$, excluding the input graph and SCC output. Empty input costs $\Theta(1)$.

The transpose $G^T$ has the same vertex set and an edge $v\to u$ for every edge $u\to v$ of $G$. On adjacency lists, allocate empty lists for every vertex and, for each $u$ and each $v\in Adj[u]$, append $u$ to $Adj^T[v]$. That pass is $\Theta(V+E)$ and produces a representation ready for the second DFS. Its explicit output representation uses $\Theta(V+E)$ words; the construction itself needs $O(1)$ working words beyond that output and the input graph. These bounds hold in every case for a nonempty graph under the same word-operation model; the empty case is constant.

Related material. Once a topological order is known, the number of paths from $s$ to $t$ in a DAG fills in linear time: initialize count[v]=0 for all vertices and then count[s]=1; process vertices in topological order, add count[u] into count[v] for every edge u->v, and return count[t]. The recurrence is ordinary DP on the DAG; a problem may ask for path counts rather than the order itself (CLRS Exercise 22.4-2). For a nonempty DAG and valid $s,t$, the full pass performs $\Theta(V+E)$ unit-cost counter/edge operations in best, average and worst cases and uses $\Theta(V)$ auxiliary counters, excluding the graph, supplied order and scalar result. This is an arithmetic-operation model, not an arbitrary-precision bit bound. If $B\ge1$ is the maximum bit length of any intermediate count, the additions take at most $O(EB)$ bit operations and the counter array at most $O(VB)$ bits; graph/index operations are separate.

A DAG has a unique topological order if and only if it has a Hamiltonian path that is forced by edges (equivalently: the topo order is unique iff there is an edge between every pair of consecutive vertices in that order). Checking uniqueness after Kahn's algorithm is easy: the indegree-0 queue must never hold more than one vertex.

To count all topological orders, work from the structure: vertices with no path between them in either direction can be interleaved freely, subject to the remaining edges.

For a general small DAG, count recursively: the number of orders equals the sum, over each current source $v$, of the number of orders of the DAG with $v$ removed. With a min-priority queue in place of Kahn's FIFO queue, the algorithm outputs the lexicographically smallest topological order.

In a DAG every edge $u\to v$ satisfies $f[u] > f[v]$ (CLRS 3e, Section 22.4): otherwise $v$ would still be grey when $u$ examines the edge, making it a back edge and creating a cycle. Sorting by decreasing $f$ therefore places $u$ before $v$.

For an SCC $C$, let $f(C)$ be the largest finish time of any vertex of $C$ in the first DFS. If the component graph has an edge $C \to C'$, then $f(C) > f(C')$ (CLRS 3e, Section 22.5). So ordering components by decreasing $f(C)$ is a topological order of the component graph. The second DFS starts at the vertex with the largest finish time, which lies in a source component $C$ of the component graph. In $G^T$ every inter-component edge is reversed, so from $C$ the search can leave only into components that are already finished, and the tree grown is exactly $C$. Repeating the argument for each new start gives one tree per SCC.

Why the transpose is needed. Running the second pass on $G$ itself fails, whether the vertices are taken in decreasing or in increasing finish order (CLRS Exercise 22.5-3 asks about the increasing order). In the five-vertex SCC example below, decreasing finish order starts the second pass at $a$ and increasing finish order starts it at $c$; in both cases DFS on $G$ reaches all five vertices, wrongly merging the two components.

Vertices $a,b,c,d,e$. Edges: $a\to b$, $a\to c$, $b\to d$, $c\to d$, $c\to e$, $d\to e$. One DFS (outer order $a,b,c,d,e$; adjacency lists alphabetical) runs as follows: discover $a$ (1), $b$ (2), $d$ (3), $e$ (4); finish $e$ (5), $d$ (6), $b$ (7); discover $c$ (8), whose edges $c\to d$ and $c\to e$ reach black vertices (cross edges); finish $c$ (9), $a$ (10). Discovery/finish times: $a: 1/10$, $b: 2/7$, $c: 8/9$, $d: 3/6$, $e: 4/5$. Decreasing finish: $a,c,b,d,e$. The only other valid order is $a,b,c,d,e$, which Kahn's algorithm with a FIFO queue produces (queue contents: $a$; then $b, c$; then $c$; then $d$; then $e$). Both respect every edge.

Vertices $a,b,c,d,e$. Edges: $a\to b$, $b\to c$, $c\to a$, $b\to d$, $d\to e$, $e\to d$. SCCs: $\{a,b,c\}$ and $\{d,e\}$. The component graph is $\{a,b,c\}\to\{d,e\}$.

First DFS (outer order $a,b,c,d,e$; lists $a: b$, $b: c, d$, $c: a$, $d: e$, $e: d$): discover $a$ (1), $b$ (2), $c$ (3); $c\to a$ is a back edge; finish $c$ (4); discover $d$ (5), $e$ (6); $e\to d$ is a back edge; finish $e$ (7), $d$ (8), $b$ (9), $a$ (10). Finish order $c, e, d, b, a$; decreasing finish order $a, b, d, e, c$.

Second DFS on $G^T$ (edges $b\to a$, $c\to b$, $a\to c$, $d\to b$, $e\to d$, $d\to e$) in the order $a, b, d, e, c$: from $a$ it reaches $c$ and then $b$, and the edge back to $a$ is already used, giving the tree $\{a, b, c\}$. The next unvisited vertex in the order is $d$; its edge to $b$ leads to a visited vertex, and it reaches $e$, giving $\{d, e\}$. Here $f(\{a,b,c\}) = 10 > f(\{d,e\}) = 8$, matching the component edge $\{a,b,c\}\to\{d,e\}$.

Comparing the two topological algorithms in an exam answer: DFS needs recursion (or an explicit stack) and produces one valid order tied to adjacency order; Kahn's algorithm makes indegrees explicit and naturally detects cycles by counting emitted vertices. Both are $\Theta(V+E)$.

Common misconceptions.