Redundant Connection: Union-Find Cycle Detection

You are given a graph that started as a tree with n nodes (labeled 1 to n), plus one extra edge. The extra edge creates exactly one cycle. Find and return that redundant edge.

This is LeetCode 684: Redundant Connection, and it is one of the best problems for learning how Union-Find detects cycles. A tree with n nodes has exactly n - 1 edges. Add one more edge and you get exactly one cycle. Your job is to find which edge completes that cycle.

Nodes 1 through 5 with edges. The dashed orange edge [2, 3] is redundant because nodes 2 and 3 are already connected through node 1.

Why this problem matters

Redundant Connection is the bridge between "I understand Union-Find" and "I can actually use it." In Number of Provinces, you use Union-Find to count connected components. Here, you use the same data structure to detect when adding an edge would create a cycle. That ability, detecting cycles as you process edges, is the foundation for Kruskal's minimum spanning tree algorithm and many dynamic connectivity problems.

The problem also teaches you to think about trees as a special case of graphs. A tree is a connected graph with no cycles. The moment you add one edge to a tree, you create exactly one cycle. The redundant edge is the one that "closes" that cycle.

The key insight

Process the edges one by one. For each edge [u, v], check whether u and v are already in the same connected component. If they are, adding this edge would create a cycle, so this is the redundant edge. If they are not, merge their components.

Union-Find gives you exactly the two operations you need:

1. Find(x): determine which component x belongs to (its root)
2. Union(x, y): merge the components of x and y

When find(u) == find(v) before calling union(u, v), both nodes are already connected. That edge is the answer.

The solution

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))
    rank = [0] * (n + 1)

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

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
        return True

    for u, v in edges:
        if not union(u, v):
            return [u, v]

Let's break this down.

Initialization: parent[i] = i for nodes 1 through n. Every node starts as its own root. We use n + 1 entries because the nodes are 1-indexed.

Find with path compression: The find function follows parent pointers up to the root. Along the way, it applies path halving (parent[x] = parent[parent[x]]), which keeps the trees flat and makes future lookups nearly O(1).

Union by rank: When merging two components, the shorter tree gets attached under the taller one. This prevents the tree from degenerating into a linked list. If the ranks are equal, we pick one as the new root and increment its rank.

The critical check: union returns False when both nodes already share the same root. That means they are already connected, and adding this edge would create a cycle. The first edge that fails the union is our answer.

Step-by-step walkthrough

Let's trace the algorithm on edges = [[1,2], [1,3], [2,3], [3,4], [4,5]]. The edge [2,3] is redundant because nodes 2 and 3 are already connected through node 1.

The algorithm stops at edge [2,3]. At that point, find(2) and find(3) both return 1, meaning both nodes are already in the same component. Adding edge [2,3] would close the cycle 1 - 2 - 3 - 1. That is our answer.

Notice that the steps after [2,3] are shown for completeness, but in practice the algorithm returns immediately when it detects the cycle.

Complexity analysis

Time: We process n edges, and each edge requires two find operations and at most one union. With path compression and union by rank, each operation runs in O(alpha(n)) amortized time, where alpha is the inverse Ackermann function. For all practical purposes, alpha(n) is a constant (it never exceeds 4 for any input that fits in memory). So the total time is effectively O(n).

Space: The parent and rank arrays each use O(n) space. No other significant data structures are needed.

The building blocks

This problem uses one core pattern with two important optimizations.

1. Union-Find with cycle detection

The key twist compared to basic Union-Find is using the return value of union to detect cycles:

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False
    parent[ry] = rx
    return True

When union returns False, both nodes are already in the same set. In a graph context, that means adding edge (x, y) would create a cycle. This pattern appears in Kruskal's MST algorithm (skip edges that would create cycles) and in problems that ask whether a graph is a valid tree.

2. Path compression

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

Path halving (parent[x] = parent[parent[x]]) flattens the tree as you traverse it. Without path compression, find could take O(n) in the worst case. With it, each call is nearly O(1) amortized. This is what makes Union-Find practical for large inputs.

3. Union by rank

if rank[rx] < rank[ry]:
    rx, ry = ry, rx
parent[ry] = rx
if rank[rx] == rank[ry]:
    rank[rx] += 1

Always attach the shorter tree under the taller one. This keeps the maximum tree height logarithmic, which bounds the worst-case find depth. Combined with path compression, this gives the near-constant amortized guarantee.

Edge cases

Before submitting, verify your solution handles:

• Minimum input: 3 nodes with edges [[1,2],[1,3],[2,3]]. The last edge [2,3] is redundant.
• Linear chain plus one edge: edges like [[1,2],[2,3],[3,4],[1,4]]. The cycle is 1-2-3-4-1, and [1,4] is the answer.
• Redundant edge is the first edge processed: this cannot happen. The problem guarantees the graph is a tree plus one edge, so the first edge always connects two unconnected nodes.
• Large cycles: the cycle might involve all n nodes. The algorithm still works because it detects the cycle at the moment the last edge of the cycle is processed.
• Multiple valid answers: the problem states to return the edge that occurs last in the input. Since we process edges in order and return the first failure, this is automatically correct.

Reading about it is not enough

You have read the solution and traced through the steps. Union-Find cycle detection makes sense right now. But will you remember the path compression line (parent[x] = parent[parent[x]]) three weeks from now? Will you remember that union returns False when it detects a cycle?

These are small details, but they are exactly the kind of thing that slips away under interview pressure. The gap between understanding and fluency is real. You can close it with spaced repetition. Practice writing the Union-Find template from scratch at increasing intervals. After a few rounds, the find and union functions come out automatically. You stop thinking about the mechanics and start thinking about the problem.

Redundant Connection is a great problem to drill because it combines the Union-Find template with a specific application (cycle detection). Once you can write the solution from memory, you are ready for harder variants like Redundant Connection II (directed graphs) and Kruskal's minimum spanning tree.

Related posts

• Number of Provinces - Uses the same Union-Find template to count connected components instead of detecting cycles
• Number of Islands - Connected components on a grid, solved with DFS flood fill. A different approach to a related problem
• Course Schedule - Cycle detection in directed graphs using DFS three-color marking, the directed counterpart to what Union-Find does here

CodeBricks breaks Redundant Connection into its Union-Find building blocks and drills them individually with spaced repetition. You practice find with path compression, union by rank, and the cycle detection check from scratch until they are automatic. When a graph connectivity problem shows up in your interview, you do not hesitate. You just write it.