= Solution
Increment a single clock on each discovery and finish, starting with clock zero. Lexicographic <depth-first search> gives
$$
\begin{array}{c|rr}
\text{vertex}&d&f\\\hline
1&1&8\\
2&9&10\\
3&2&7\\
4&11&12\\
5&3&4\\
6&5&6
\end{array}
$$
The first search tree has discovery <edges> $1\to3$, $3\to5$, $3\to6$. The edge $5\to1$ returns to an active ancestor. Once that tree finishes, vertex $2$ is a new root whose neighbour $1$ is already finished, and vertex $4$ is the final root. This accounts for all twelve events in the <DFS discovery and finishing times>.
Back to article page
