# Strong Components in Linear Time

Explore the different techniques used to implement strong components in linear time efficiently.

## 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$.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy