Pattern7 min read

Union-Find (Disjoint Set Union)

A near-O(1) data structure for connectivity questions — used in Kruskal, percolation, and dynamic graph problems.

graphunion-finddsu

Intro

Union-Find groups elements into disjoint sets and supports two operations: find(x) returns the representative of x's set, and union(x, y) merges the two sets. With path compression + union by rank, both run in essentially O(α(n)) — practically constant.

Key insight

If the question is 'are two things connected?' and the graph is built incrementally or reasoning by edges (not paths), reach for DSU before BFS/DFS.

Approach

1Initialise parent[i] = i and rank[i] = 0.
2find(x): walk parent pointers up; assign each node directly to the root on the way back (path compression).
3union(a, b): find roots; attach the lighter tree under the heavier one (union by rank).

Complexity

Time

O(α(n)) per op — effectively O(1)

Space

O(n)

Code

Snippetjava

class DSU {
    int[] parent, rank;
    DSU(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) { parent[ra] = rb; }
        else if (rank[ra] > rank[rb]) { parent[rb] = ra; }
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }
}

Pitfalls

Forgetting path compression — find degrades to O(n).
Comparing `parent[x] == x` only at the top level — must follow until you find the root.
Counting unions but not components — usually you want components = initial - successful unions.

Variants & follow-ups

Number of Connected Components (LC 323)
Accounts Merge (LC 721)
Redundant Connection (LC 684)