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

In depth-first search, mark every vertex white initially. At a white start vertex $u$, increment a global clock, record $d[u]$ and color it gray. Scan its outgoing adjacency list; recursively visit each still-white neighbor, recording the discovery edge. After all neighbors have been processed, color $u$ black, increment the clock and record $f[u]$. Start again from every remaining white vertex to obtain a forest. Each vertex is discovered once and each edge scanned once, so the time is $O(|V|+|E|)$ with adjacency lists.

The DFS parenthesis property says that for distinct vertices $u,v$, their intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are disjoint or one lies strictly inside the other. Moreover $v$ is a proper descendant in a rooted tree of $u$ exactly when $d[u]<d[v]<f[v]<f[u]$. A recursive call finishes before its caller returns, while completed calls from separate branches have disjoint intervals; these two possibilities prove the property.