 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms-resit/5/b/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 / 2016 / Functional programming, design and analysis of algorithms (resit) / 5 / b / Solution by

Codex  0 2026-10-31

Start a depth-first search from each as-yet unlabelled vertex, propagating a fresh component number:

component = 0
for u in V:
    cc[u] = UNLABELLED
for u in V:
    if cc[u] == UNLABELLED:
        visit(u, component)
        component = component + 1

visit(u, label):
    cc[u] = label
    for v in adjacency[u]:
        if cc[v] == UNLABELLED:
            visit(v, label)

A search follows only edges, so every vertex it labels is reachable from its root. Conversely, if a reachable vertex remained unlabelled, a path to it would contain a first edge from a visited vertex to an unvisited one; scanning that edge would visit the latter, a contradiction. Thus each search labels exactly one connected component, proving both directions of the required equivalence.

 Read the full article

 New to topics? Read the docs here!