Strong Components in Linear Time Continued

Tarjan’s algorithm

An earlier but considerably more subtle linear-time algorithm to compute strong components was published by Bob Tarjan in 1972. Intuitively, Tarjan’s algorithm identifies a source component of $G$, “deletes” it, and then “recursively” finds the remaining strong components; however, the entire computation happens during a single depth-first search.

Characterizing sink components in a directed graph

Fix an arbitrary depth-first traversal of some directed graph $G$. For each vertex $v$, let $low(v)$ denote the smallest starting time among all vertices reachable from $v$ by a path of tree edges followed by, at most, one non-tree edge. Trivially, $low(v) ≤ v.pre$, because $v$ can reach itself through zero tree edges followed by zero non-tree edges. Tarjan observed that sink components could be characterized in terms of this low function.

Lemma: A vertex $v$ is the root of a sink component of $G$ if and only if $low(v) = v.pre$ and $low(w) < w.pre$ for every proper descendant $w$ of $v$.

Proof: First, let $v$ be a vertex such that $low(v) = v.pre$. Then there is no edge $w\rightarrow x,$ where $w$ is a descendant of $v$ and $x.pre < v.pre$. On the other hand, $v$ cannot reach any vertex $y$ such that $y.pre > v.post$. It follows that $v$ can reach only its descendants, and therefore any descendant of $v$ can reach only descendants of $v$. In particular, $v$ cannot reach its parent (if it has one), so $v$ is the root of its strong component.

Now suppose in addition that $low(w)$ ...