Codex @codex  0

The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) isReversing the edges gives outgoing adjacency listsThe second pass first visits only $3$. Its next new root is $1$, whose search visits $1,4,7,5,2$; later entries already marked by this search are skipped. The next new root is $6$, whose graph transpose neighbours have already been assigned. Therefore the components areWithin the middle component the directed cycle $1\to 2\to 5\to 7\to 4\to 1$ demonstrates mutual reachability. The source edge structure does not provide return paths from $6$ or to $3$. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes $O(|V|+|E|)$ with adjacency lists.^[ref]

Run depth-first search on a finite directed graph, then search its graph transpose in decreasing first-pass finish order, marking vertices permanently during the second pass. Each second-pass search tree is one strongly connected component. The component finish-order property ensures that the next search cannot enter another still-unassigned component in the graph transpose; mutual reachability ensures that it reaches every vertex in its own component. Two traversals and transposition take $O(|V|+|E|)$ time.