The tunnel to seal

A campus grew one service tunnel at a time and ended up with a loop. Sealing a tunnel on the loop costs nothing; sealing any other one strands a building.

The problem

A campus has n buildings numbered 1 to n. The estates office kept a dig log of exactly n entries, each a pair of buildings joined by a tunnel, in the order the tunnels were dug. No pair was joined twice and no tunnel starts and ends at the same building.

With n buildings, n tunnels and every building reachable from every other, exactly one loop runs through the campus. The office wants to seal one tunnel and keep everything reachable. Several tunnels qualify, and they want the one dug last among those, because it is the newest and cheapest to decommission.

Return that tunnel as the log recorded it, buildings in the log's own order.

Input. tunnels — a list of [a, b] pairs in dig order.

Output. The pair to seal.

Example.

tunnels = [[1, 2], [2, 3], [1, 3]]   ->  [1, 3]

The loop is 1-2-3-1, so any of the three could go; [1, 3] is the newest.

Example. The newest tunnel is usually not the answer:

tunnels = [[1, 4], [3, 4], [1, 3], [1, 2], [4, 5]]   ->  [1, 3]

[1, 2] and [4, 5] are the only tunnels serving buildings 2 and 5, so sealing either strands one. The loop is 1-4-3-1 and its newest member is [1, 3].

Constraints.

• 3 <= len(tunnels) <= 1000
• buildings are numbered 1 to len(tunnels)
• 1 <= a, b <= n and a != b, with no pair repeated
• the tunnels connect every building and contain exactly one loop

Hints

Approach

Brute force

Walk the log backwards. Delete each candidate in turn, run a traversal from building 1, and keep the first candidate that still reaches all n buildings. Each check costs O(n) and up to n candidates get checked: O(n^2), a million steps at n = 1000, and it rebuilds the whole structure every time.

The insight

Read the log forwards: the first entry whose two ends are already joined is the newest tunnel on the loop, and therefore the answer.

A tunnel is sealable exactly when it lies on the loop — remove any other and the two sides fall apart. Before the loop closes, the entries read so far form a forest, so every entry joins two separate groups. The first entry that does not is the one closing the loop, and the rest of that loop is the path already joining its ends, every tunnel of which was dug earlier. So this entry is the newest member of the only loop there is.

Algorithm

1. Give every building its own group.
2. Read the log in order and find the group root of each end.
3. If the two roots match, this entry closes the loop: return it.
4. Otherwise point one root at the other and carry on.
5. Compress the path on the way out of each find so later lookups stay flat.

Complexity

Time O(n a(n)) — one find-and-merge per log entry, effectively constant with path compression. Space O(n) for the parent array, nothing else.

Solution

"""The tunnel to seal — the first log entry whose two ends are already joined."""


def find(parent, node):
    """Root of the node's group, flattening the path walked on the way back."""
    root = node
    while parent[root] != root:
        root = parent[root]
    while parent[node] != root:
        parent[node], node = root, parent[node]
    return root


def solve(tunnels):
    parent = list(range(len(tunnels) + 1))     # buildings are numbered 1..n
    for a, b in tunnels:
        # Invariant: the entries read so far, minus the one loop-closer, form a
        # forest. So two ends already in one group means this entry closes the
        # loop, and every earlier entry on that loop was dug before it.
        root_a, root_b = find(parent, a), find(parent, b)
        if root_a == root_b:
            return [a, b]
        parent[root_a] = root_b
    return []

TESTS = [
    (([[1, 2], [2, 3], [1, 3]],), [1, 3]),                        # smallest campus
    (([[1, 4], [3, 4], [1, 3], [1, 2], [4, 5]],), [1, 3]),        # loop closed early
    (([[1, 2], [2, 3], [3, 4], [1, 4], [4, 5]],), [1, 4]),
    (([[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]],), [1, 5]),        # loop closed last
    (([[1, 3], [2, 3], [1, 2], [3, 4]],), [1, 2]),
    (([[2, 3], [1, 2], [1, 3], [3, 4], [4, 5]],), [1, 3]),
]

Pitfalls

• Returning the last entry in the log. On [[1, 4], [3, 4], [1, 3], [1, 2], [4, 5]] that gives [4, 5] and building 5 loses its only tunnel. Newest sealable is not newest.
• Writing parent[a] = find(b) instead of parent[find(a)] = find(b). Re-pointing the node rather than its root leaves the rest of a's old group hanging off the old root, so two joined buildings stop testing as joined and the loop is detected late or missed entirely.
• Sizing the parent array to n rather than n + 1. Buildings are numbered from 1, so the last building indexes one past the end.

Variants

• Merging the choir roster — the same structure keyed by strings, asked for the groups rather than the loop.
• Union-find — the structure itself, and when it beats rerunning a traversal.