Disjoint Set (Union–Find)

The problem

Imagine a social network where friendships keep forming. You keep asking: “Are Asha and Ravi in the same friend circle?” and “Merge these two circles.” With millions of people, re-scanning everyone each time is far too slow.

A Disjoint Set Union (DSU), also called Union–Find, answers both questions in nearly constant time.

The idea: each set is a tree

Every element has a parent pointer. Elements in the same set form a tree, and the root (which points to itself) is the set’s representative. In the model, arrows point to the parent and the purple nodes are roots.

Two operations:

• find(x): follow parent pointers up to the root. Two elements are in the same set exactly when find(a) == find(b).
• union(a, b): find both roots; if they differ, make one root point to the other. The sets are now merged.

Two optimisations that make it lightning fast

1. Union by rank (or by size)

Keep a rank (an upper bound on the tree height) for every root. When merging, attach the shorter tree under the taller one. The height only grows when two trees of equal rank merge. This alone keeps trees at height O(log n).

2. Path compression

During find(x), after reaching the root, make every node on the path point directly to the root. The tree becomes almost flat, so later finds take one or two steps. Try running Find twice on a deep node in the model.

With both optimisations, a sequence of operations costs O(α(n)) each, where α is the inverse Ackermann function — it is at most 4 for any number you could ever store. In practice: constant time.

Code

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                 # already in the same set
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                             # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

d = DSU(10)
d.union(0, 1); d.union(2, 3); d.union(1, 3)
print(d.find(0) == d.find(2))   # True  — same set
print(d.find(0) == d.find(5))   # False

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

struct DSU {
    vector<int> parent, rnk;
    DSU(int n) : parent(n), rnk(n, 0) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;                                     // union by rank
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

int main() {
    DSU d(10);
    d.unite(0, 1); d.unite(2, 3); d.unite(1, 3);
    cout << (d.find(0) == d.find(2)) << "\n";   // 1
}

Where is Union–Find used?

• Kruskal’s minimum spanning tree: add the cheapest edge whose endpoints are in different sets (otherwise it would form a cycle).
• Connected components in networks, images (labelling blobs of pixels) and maps.
• Cycle detection in undirected graphs.
• Social networks (friend circles), percolation simulations, and grouping equivalent items (e.g. “accounts merge”).

Common mistakes

• Comparing parent[a] == parent[b] instead of find(a) == find(b) — parents may differ even in the same set.
• Forgetting to find the roots before linking, which can create cycles in the parent pointers.
• Recursive find hitting Python’s recursion limit on huge naive chains — use iteration or the optimisations.