Strong Components in Linear Time

Lemma for computing strong components

In fact, there are several algorithms to compute strong components in $O(V + E)$ time, all of which rely on the following observation.

Lemma 1: Fix a depth-first traversal of any directed graph $G$. Each strong component $C$ of $G$ contains exactly one node that does not have a parent in $C$. (Either this node has a parent in another strong component, or it has no parent.)

Proof: Let $C$ be an arbitrary strong component of $G$. Consider any path from one vertex $v ∈ C$ to another vertex $w ∈ C$. Every vertex on this path can reach $w$, and thus can reach every vertex in $C$; symmetrically, every node on this path can be reached by $v$, and thus can be reached by every vertex in $C$. We conclude that every vertex on this path is also in $C$.

Let $v$ be the vertex in $C$ with the earliest starting time. If $v$ has a parent, then $parent(v)$ starts before $v$, and thus can’t be in $C$.

Now, let $w$ be another vertex in $C$. Just before $DFS(v)$ is called, every vertex in $C$ is new, so there is a path of new vertices from $v$ to $w$. The Lemma from the lesson “Preorder and Postorder” now implies that $w$ is a descendant of $v$ in the depth-first forest. Every vertex on the path of tree edges $v$ to $w$ lies in $C$; in particular, $parent(w) ∈ C$.

Conclusion of Lemma

The previous lemma implies that each strong component of a directed graph $G$ defines a connected subtree of any depth-first forest of $G$. In particular, for any strong component $C$, the vertex in $C$ with the earliest starting time is the lowest common ancestor of all vertices in $C$; we call this vertex the root of $C$.