Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 6 / a / i

Increment a single clock on each discovery and finish, starting with clock zero. Lexicographic depth-first search givesThe first search tree has discovery edges $1\to 3$, $3\to 5$, $3\to 6$. The edge $5\to 1$ 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.