= Solution
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.
Back to article page
