Redundant Connection (LC 684)

Pattern: Union-Find — Detecting the Cycle Edge Difficulty: Medium Key Concept: Add edges one by one. The first edge whose two endpoints are already in the same Union-Find component is the redundant one.

Problem Statement

A connected graph that was a tree has had one extra edge added. You are given the edges in the order they were added. Return the last edge in the input that completes a cycle.

Example

• edges = [[1,2],[1,3],[2,3]] → [2,3]
• edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] → [1,4]

---

1. Algorithm & Pseudocode

dsu = DSU(n)
for each edge (u, v) in input order:
    if !dsu.union(u, v):       // find(u) == find(v) already
        return (u, v)

dsu.union returns false iff the two nodes already share a root — adding this edge would close a cycle.

---

2. Step-by-Step Analysis

Why Union-Find is perfect here We need online cycle detection as edges are added. Union-Find does this in amortized O(α(N)).

Why “first edge that fails to union” The problem says edges are given in the order they were added. The cycle is created the moment we try to union two nodes that are already connected. By the problem’s guarantee, only one such edge exists.

Edge count is n A tree on n nodes has n - 1 edges. With one extra, the total is n. We process every edge — at least one will close a cycle.

ASCII Trace for edges = [[1,2],[1,3],[2,3]]

parent (1-indexed) start: [_,1,2,3]

edge (1,2): find(1)=1, find(2)=2 → union → parent[2]=1   parent = [_,1,1,3]
edge (1,3): find(1)=1, find(3)=3 → union → parent[3]=1   parent = [_,1,1,1]
edge (2,3): find(2)=1, find(3)=1 → SAME → return (2,3)

---

3. Java Solution

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        int[] rank = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra == rb) return e;          // cycle edge
            if (rank[ra] < rank[rb]) parent[ra] = rb;
            else if (rank[ra] > rank[rb]) parent[rb] = ra;
            else { parent[rb] = ra; rank[ra]++; }
        }
        return new int[0]; // problem guarantees an answer
    }
    private int find(int[] p, int x) {
        if (p[x] != x) p[x] = find(p, p[x]);
        return p[x];
    }
}

Time: (O(n \cdot α(n)) ≈ O(n)) Space: (O(n))

---

4. The “Java vs. Others” Edge

• Node labels are 1-indexed; size arrays [n+1] to align.
• Path compression in find keeps the trees flat — practical performance is near-constant per op.
• For LC 685 (directed variant), Union-Find alone isn’t enough — you’d need to detect “node with in-degree 2” as a special case first.

---

5. Complexity Summary

Approach	Time	Space	Notes
Union-Find	O(n α(n))	O(n)	Canonical answer
DFS	O(n²) worst	O(n)	Re-search the tree on each edge add