Redundant Connection

Redundant Connection hands you a graph that is almost a tree — it has one edge too many — and asks you to find that extra edge. It is the perfect first taste of union-find (also called Disjoint Set Union), the go-to tool for "are these two things already connected?"

The slow way first

You could rebuild the graph and, after adding each edge, run a full search (BFS or DFS) to check whether the two endpoints were already reachable. The first edge for which they were is the redundant one. That works, but each check is O(n) and there are n edges, so it is O(n²).

The question to ask: as I add edges one by one, how do I cheaply know whether two nodes are already in the same connected group? That is exactly what union-find answers — in nearly O(1) per query.

The idea: union-find

Keep a parent array where each node starts as its own root. Two operations:

• find(x) — follow parent pointers up until you reach a node that is its own root. That root names the group x belongs to.
• union(a, b) — point one root at the other, merging the two groups.

Process the edges in order. For edge (u, v), compute find(u) and find(v). If the roots are equal, u and v are already connected — this edge closes a cycle, so it is the redundant one. Otherwise, union them and move on. Because we scan in input order, the first such edge we hit is automatically the last valid answer.

The key insight: a cycle appears the instant we try to connect two nodes that already share a root. Union-find spots that in near-constant time.

Walk through it

Step through the animation. Edges (1, 2) and (1, 3) join nodes from different groups, so we union them — after both, nodes 1, 2, and 3 all share root 1. When we reach (2, 3), find(2) and find(3) both walk up to 1. Same root! That edge is the redundant one, so we flag it and return [2, 3].

Pseudocode

parent[x] = x for every node          # each node is its own group
 
define find(x):
    while parent[x] is not x:          # walk up to the root
        x = parent[x]
    return x
 
for each edge (u, v) in edges:
    ru, rv = find(u), find(v)
    if ru == rv:                       # u and v already connected
        return [u, v]                  # this edge closes the cycle
    parent[rv] = ru                    # otherwise merge the two groups

The Python solution

def find_redundant(edges):
    parent = list(range(len(edges) + 1))
 
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
 
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]
        parent[rv] = ru

• parent is sized len(edges) + 1 so node labels 1..n index directly (slot 0 is unused).
• find walks parent pointers up to the root that names a node's group.
• ru, rv = find(u), find(v) gets the group of each endpoint of the current edge.
• Line 11 is the heart of it: if the two roots are equal, the nodes are already connected, so this edge is redundant — return it (line 12).
• Otherwise parent[rv] = ru merges the two groups, and we continue.

Complexity

a(n) is the inverse Ackermann function — effectively a small constant, so union-find is treated as nearly O(n) overall. We use O(n) extra space for the parent array.

When this pattern shows up

Practice