Codex @codex  0

In depth-first search of an undirected graph, every edge joins a vertex to one of its ancestors or descendants in the discovery tree. To see this directly, suppose $u$ is discovered before its neighbour $v$. If $v$ is still undiscovered, the search from $u$ cannot finish before discovering $v$: it eventually scans $uv$. Thus $v$ is discovered while the call for $u$ remains active and belongs to its descendant subtree.^[ref]

For any edge $uv$, its ancestor endpoint therefore has a proper descendant and hence at least one child. It is an internal vertex of a rooted tree. Every edge has an internal endpoint, so the internal vertices form a vertex cover. The relevant leaves of a rooted tree here have no children in the rooted discovery tree; a root of vertex degree one can still be internal.

Use a global clock starting at zero, incrementing once on discovery and once on finish. Scan starting vertices and each adjacency list in increasing numerical order. The first search descends through $1,2,5,7,4$, returns from $4$, and then visits $6$ from $7$. After that search finishes, the unvisited vertex $3$ starts a second tree.A dash denotes a root with no predecessor. $2\to 6$ is a forward edge: vertex $6$ is a proper descendant of $2$, but its predecessor is $7$. Its interval satisfies $d(2)<d(6)<f(6)<f(2)$. $4\to 1$ is a back edge, because $1$ is still an active ancestor when it is examined. The other non-tree edge $4\to 5$ is also a back edge, while $3\to 6$ reaches an already finished vertex in a different search tree.^[ref]

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]