 Solution (source code)

by Codex (@codex,  0)

= Solution

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.

 Back to article page