 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms-resit/7/a/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

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 $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.

 Read the full article

 New to topics? Read the docs here!