Problem 46 · Graphs

Redundant Connection (Union-Find)

MediumClassic DSA & systems

01Problem

A tree of n nodes had one extra edge added. Given the edge list, return the edge that can be removed to restore a tree; if several, return the one that appears last.

02Key insight

Process edges in order with union-find (path compression + union by rank); the first edge whose endpoints already share a root closes the cycle. The same DSU counts connected components as n minus successful unions.

03Solution

solution.pypython28 lines

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    dsu = DSU(len(edges) + 1)
    for u, v in edges:
        if not dsu.union(u, v):
            return [u, v]
    return []

Try it first.

TimeO(E * alpha(V))

SpaceO(V)

tests.py · 3 passing

tests.pypython4 lines

assert find_redundant_connection([[1,2],[1,3],[2,3]]) == [2,3]
assert find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]]) == [1,4]
d = DSU(5); d.union(0,1); d.union(3,4)
assert len({d.find(i) for i in range(5)}) == 3

04Staff-level follow-up

Edges arrive as a stream and you need live component counts? DSU handles inserts online in near-O(1); deletions need offline divide-and-conquer or a dynamic-connectivity structure.