= Solution
Apply the <two-pass strongly connected component algorithm>:
1. Run <depth-first search> over all vertices of $G$, recording their finish order.
2. Construct the <graph transpose> by reversing every edge.
3. Mark every vertex unvisited again. In decreasing first-pass finish order, start a transpose search whenever the next vertex is unvisited. The vertices newly reached by each search form one <strongly connected component>.
The finish order prevents a second-pass search from entering a different still-unassigned component, while mutual reachability makes it visit the entire current component. With <adjacency lists>, each traversal and the transposition scan takes $O(|V|+|E|)$ time. Thus the total worst-case time is \b[$\Theta(|V|+|E|)$], including isolated vertices.
Back to article page
