= Solution
Use the <two-pass strongly connected component algorithm>. First run a complete <depth-first search> of $G$, starting a new search at each unvisited <vertex> as necessary. Append each <vertex> to a <list> when its recursive call finishes. Next construct the <graph transpose> $G^T$ by reversing every <edge>. Reset all visited flags. Process the <vertices> in decreasing first-pass finishing order, running <depth-first search> in $G^T$ from each still-unvisited <vertex>. The newly reached <vertices> in each such search form one <strongly connected component>.
To prove this, contract each <strongly connected component> to one <vertex>. The resulting <condensation graph> is a <Directed acyclic graph>, because a directed <graph cycle> of distinct components would make them mutually reachable and hence a single component. For a component $C$, write $F(C)$ for its largest first-pass finishing time. If there is an <edge> $C\to D$ between distinct components, then $F(C)>F(D)$. Indeed, if the first search reaches $C$ before $D$, it can reach $D$, which must finish before the search in $C$ finishes. If it reaches $D$ first, $D$ cannot reach $C$ or they would be the same component, so $D$ finishes before $C$ is discovered.
Among unreported components, the one with greatest $F$ therefore has no incoming <edge> from another unreported component in $G$. In the <graph transpose> it has no outgoing <edge> to any other unreported component. A second-pass search cannot escape it, while strong connectivity lets that search reach all its <vertices>. Earlier reported components are ignored by the visited flags. Repeating this argument proves
$$
\boxed{\text{each second-pass search returns exactly one SCC, and all SCCs are returned}.}
$$
Both <depth-first searches> visit every <vertex> and scan every <edge> once, and transposition costs $\Theta(|V|+|E|)$. Therefore the total <time complexity> is $\boxed{\Theta(|V|+|E|)}$ with <adjacency lists>. Storage for the transpose is $O(|V|+|E|)$, while visited flags, finishing order and the search stack use $O(|V|)$ additional space. No sorting is needed: reverse the <list> recorded at finishing time.
Back to article page
