= Solution
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) is
$$
3,1,2,5,7,6,4.
$$
Reversing the <edges> gives outgoing <adjacency lists>
$$
1:(4),\quad2:(1),\quad3:(),\quad4:(7),\quad5:(2,4),\quad6:(2,3,7),\quad7:(5).
$$
The 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 are
$$
\boxed{\{3\},\qquad\{1,2,4,5,7\},\qquad\{6\}.}
$$
Within the middle component the <directed cycle> $1\to2\to5\to7\to4\to1$ 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>.<Depth-first search by Jeff Erickson>[§§6.5–6.6, strong components, condensation and the two-search construction]{ref}
Back to article page
