= Solution
Maintain white, gray and black colors for undiscovered, active and completed vertices. A single traversal clock records <DFS discovery and finishing times>:
``
for v in V: color[v] = white; parent[v] = none
time = 0
visit(u):
time = time+1; d[u] = time; color[u] = gray
for v in adjacency[u]:
if color[v] == white:
parent[v] = u
visit(v)
color[u] = black; time = time+1; f[u] = time
for u in V:
if color[u] == white: visit(u)
``
The outer loop makes a <depth-first search> forest even when the directed graph is disconnected. Each vertex is entered once and each directed adjacency entry is inspected once. Thus an <adjacency list> representation gives \b[$O(|V|+|E|)$ time] and $O(|V|)$ auxiliary storage, including the worst-case recursive stack. Sorting neighbors to impose a particular visit order would be additional work.
Back to article page
