Union-Find · Redundant Connection

A tree of N nodes has exactly N-1 edges. Add one more and you create a cycle. Union-Find processes edges in order and flags the first one whose endpoints are already connected.

Concept

Two operations

find(x) returns the representative root of x's set. union(a,b) merges two sets. Two nodes are connected iff they share the same root.

Process edges one by one; if find(u) == find(v) before uniting, that edge closes a cycle, it's the redundant one.

Two optimizations

Path compression: flatten the tree on find
Union by rank/size: attach smaller under larger
Together → near O(1) amortized per op
Answer = the edge that hit a same-root check

Interactive

Union edges until one loops back

Not yet added Considering United Redundant

slowfast

Step 0

Unions done

Sets left

–

Edge

–

Redundant

–

Implementation

C++

class DSU {
    vector<int> parent, rnk;
public:
    DSU(int n) : parent(n), rnk(n, 0) {
        iota(parent.begin(), parent.end(), 0);  // each its own root
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // path compress
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;             // already connected → cycle
        if (rnk[a] < rnk[b]) swap(a, b);      // union by rank
        parent[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    DSU dsu(edges.size() + 1);
    for (auto& e : edges)
        if (!dsu.unite(e[0], e[1]))
            return e;                       // first edge forming a cycle
    return {};
}

Complexity

Time

O(E · α(V))

α is the inverse Ackermann function, effectively constant.

Space

O(V)

Parent and rank arrays, one slot per node.

Answer

first cycle

The earliest edge whose ends already share a root.

Notes

Path compression + union by rank together give near-constant ops. Using only one still works but is slower.
DSU is the go-to for dynamic connectivity: "are these two nodes connected?" as edges stream in.
Redundant Connection guarantees exactly one extra edge, so the first same-root hit is the unique answer.
Powers Kruskal's MST, number of connected components, and account/email merging problems.
For the directed variant (LC 685) you also track indegree, plain DSU isn't enough there.