Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 6 / b / 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 $\Theta (|V|+|E|)$, including isolated vertices.