= 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.
$$
\begin{array}{c|rrrrrrr}
v&1&2&3&4&5&6&7\\\hline
\pi(v)&-&1&-&7&2&7&5\\
d(v)&1&2&13&5&3&7&4\\
f(v)&12&11&14&6&10&8&9
\end{array}
$$
A dash denotes a root with no predecessor. \b[$2\to6$ 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)$. \b[$4\to1$ is a back <edge>], because $1$ is still an active ancestor when it is examined. The other non-tree <edge> $4\to5$ is also a back <edge>, while $3\to6$ reaches an already finished <vertex> in a different search tree.<Depth-first search by Jeff Erickson>[§6.1, discovery/finish intervals and edge classification]{ref}
Back to article page
