Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 7 / a / Solution

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]