Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 8 / e / 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 provesBoth 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.