Redundant Connection: Find the Edge That Closes a Cycle with Union-Find

Problem

A tree with nodes labelled 1 to n had exactly one extra edge added between two different existing nodes, so the graph now has n edges and exactly one cycle. Given the edges in order, return an edge whose removal turns the graph back into a tree. If several edges would work, return the one that appears last in the input.

This is widely known as LeetCode 684, “Redundant Connection”.

Assume 3 to 1,000 nodes.

Examples

edges [[1,2],[2,3],[3,4],[1,4],[1,5]]
cycle: 1-2-3-4-1; candidates [1,2],[2,3],[3,4],[1,4]; last in input: [1,4]
-> [1,4]

edges [[1,2],[1,3],[2,3]]
-> [2,3]

edges [[2,4],[1,2],[4,1],[3,1]]
cycle 1-2-4-1, last cycle edge in input: [4,1]
-> [4,1]

Approach 1: try removing edges from the end

Walk the edges from last to first. For each, check whether the graph without that edge is connected (a connected graph with n - 1 edges is a tree). The first one that works is the answer.

def redundant_brute(edges):
    n = len(edges)
    for skip in range(n - 1, -1, -1):
        graph = {v: [] for v in range(1, n + 1)}
        for i, (a, b) in enumerate(edges):
            if i != skip:
                graph[a].append(b)
                graph[b].append(a)
        seen, stack = {1}, [1]
        while stack:
            for nxt in graph[stack.pop()]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
        if len(seen) == n:
            return edges[skip]
    return []

Each check is O(n), so the whole thing is O(n^2).

Approach 2: optimal, union-find

Why the first failed union is the answer

Before the cycle is complete, every edge joins two separate trees, so unions succeed. The edge that completes the cycle is the first one whose endpoints are already connected. All other cycle edges appeared earlier in the input, so this edge is the last cycle edge in input order, which is exactly the tie-break the problem asks for.

Template

for (a, b) in edges:
    if find(a) == find(b): return [a, b]
    union(a, b)

Python solution

def find_redundant_connection(edges):
    n = len(edges)
    parent = list(range(n + 1))          # nodes are 1-based
    size = [1] * (n + 1)

    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
    return []

Complexity

• Time: O(n * α(n)), effectively linear.
• Space: O(n).

Tests

for fn in (find_redundant_connection, redundant_brute):
    assert fn([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
    assert fn([[1, 2], [1, 3], [2, 3]]) == [2, 3]          # smallest cycle
    assert fn([[2, 4], [1, 2], [4, 1], [3, 1]]) == [4, 1]
    # Cycle not involving node 1, extra edge in the middle of the list
    assert fn([[1, 2], [2, 3], [3, 4], [4, 2], [4, 5]]) == [4, 2]

# Larger ring: the closing edge is the last
ring = [[i, i + 1] for i in range(1, 500)] + [[500, 1]]
assert find_redundant_connection(ring) == [500, 1]

Edge cases and pitfalls

• 1-based labels. Size the parent array n + 1, or shift labels down by one.
• Returning the first cycle edge instead of the last. Union-find gives the right one for free, but a DFS that finds the cycle must then pick the cycle edge with the largest input index.
• Directed edges. If edges are directed (each node has one parent), the problem becomes Redundant Connection II with a node possibly having two parents, and plain union-find is not enough.

Where this shows up in data engineering

When a hierarchy table (employee to manager, account to parent account) should be a tree, loading rows in order with union-find flags the exact row that introduces a loop. That is a cheap data-quality check to run before building a recursive rollup.