Disjoint Set Union (Union-Find)

How union-find maintains a partition of elements under merges, why path compression and union by size make operations nearly constant, and where it is used — Kruskal's algorithm, connectivity and cycle detection.

What you will learn

Prerequisites: Module 11 (trees as parent arrays).

Operations

make-set, find, union; connected components; path compression; union by size/rank.

Syntax

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

With path compression and union by size/rank, operations are amortized O(α(n)), where α is the inverse Ackermann function. α(n) ≤ 4 for any n that fits in the universe, so in practice each operation is constant time; the run shows parent chains stay extremely short even after a million unions.

Output (CPython 3.13.1): Python's default recursion limit is 1000 frames, so the C++ recursive find would fail on a long chain before compression; the iterative two-pass version avoids recursion entirely.

The recursive find can recurse deeply before compression flattens the path; union by size alone already bounds the depth by log₂ n, so the recursion is safe here. An iterative two-pass find avoids recursion entirely.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    explicit DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    DSU d(8);
    vector<pair<int, int>> edges = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {0, 2}, {6, 7}, {5, 6}};
    for (auto [a, b] : edges) {
        bool merged = d.unite(a, b);
        cout << "union(" << a << ", " << b << "): " << (merged ? "merged" : "already connected -> this edge closes a cycle") << '\n';
    }
    set<int> roots;
    for (int i = 0; i < 8; ++i) roots.insert(d.find(i));
    cout << "components: " << roots.size() << ", size of 0's component: " << d.sz[d.find(0)] << '\n';
    cout << boolalpha << "connected(3, 0)=" << (d.find(3) == d.find(0)) << " connected(3, 7)=" << (d.find(3) == d.find(7)) << '\n';

    // 10^6 random unions and finds: near-c
…

union(0, 1): merged
union(2, 3): merged
union(1, 3): merged
union(4, 5): merged
union(0, 2): already connected -> this edge closes a cycle
union(6, 7): merged
union(5, 6): merged
components: 2, size of 0's component: 4
connected(3, 0)=true connected(3, 7)=false
1e6 random unions: 838182 merges, components 161818, deepest parent chain 4

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

    def find(self, x):                     # iterative: no recursion limit on long chains
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:      # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def unite(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

d = DSU(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (0, 2), (6, 7), (5, 6)]:
    print(f"union({a}, {b}):", "merged" if d.unite(a, b) else "already connected")
print("components:", len({d.find(i) for i in range(8)}))

union(0, 1): merged
union(2, 3): merged
union(1, 3): merged
union(4, 5): merged
union(0, 2): already connected
union(6, 7): merged
union(5, 6): merged
components: 2

Applications

Kruskal's MST, connectivity, cycle detection in undirected graphs, component counting, offline connectivity, and successor/painting problems.

Practice

Easy: number of provinces in an adjacency matrix.

Medium: accounts merge — group email addresses that belong to the same person.

Hard: “painting” queries: paint ranges in reverse order, using DSU to jump over already-painted cells.

Quiz

? `unite(a, b)` returns false. What does that tell you about the edge (a, b) in an undirected graph?
+ a and b were already connected, so the edge closes a cycle :: The basis of DSU cycle detection and Kruskal's skip rule.
- The edge is invalid. :: It is valid.
- a equals b. :: Not necessarily.
- The DSU is full. :: No such concept.

? What does path compression do?
+ Points every node on the find path directly at the root :: Later finds are shorter.
- Merges two sets :: That is union.
- Sorts the elements :: No.
- Deletes elements :: DSU does not support deletion directly.

? Which operations does a plain DSU support efficiently? (select all that apply)
+ Merge two sets :: unite.
+ Test whether two elements share a set :: Compare finds.
- Split a set into two :: Not supported (see rollback DSU or link-cut trees).
+ Count components :: Track merges.