Union-find (disjoint sets)

Many problems boil down to one question asked over and over while things get glued together: are these two in the same group yet? Cities joined by new roads, pixels merging into regions, accounts that share an email, edges added to a graph. Union-find — also called a disjoint-set forest — answers it in practically constant time per operation, with about twenty lines of code.

1. The problem

We have elements 0 .. n-1, each starting in its own set, and two operations:

• unite(a, b) — merge the set containing a with the set containing b.
• find(x) — return a representative of x's set, so that a and b are connected exactly when find(a) == find(b).

Sets only ever merge. There is no "split" — that restriction is what makes the structure so fast (and is the one thing to check before reaching for it).

2. A forest of parent pointers

Store one number per element: its parent. Each set is a tree; the root points at itself and is the set's representative.

find follows parent links to the root. unite finds both roots and, if they differ, makes one root the child of the other:

#include <cstddef>
#include <numeric>
#include <print>
#include <vector>

struct Naive {
    std::vector<std::size_t> parent;
    explicit Naive(std::size_t n) : parent(n) { std::iota(parent.begin(), parent.end(), std::size_t{0}); }

    std::size_t find(std::size_t x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }
    bool unite(std::size_t a, std::size_t b) {
        std::size_t ra = find(a), rb = find(b);
        if (ra == rb) return false;   // already one set
        parent[ra] = rb;
        return true;
    }
};

int main() {
    Naive s(6);
    s.unite(0, 1);
    s.unite(1, 2);
    s.unite(3, 4);
    std::println("0~2: {}  0~3: {}", s.find(0) == s.find(2), s.find(0) == s.find(3));
    std::println("parent = {}", s.parent);
}

Correct — but look at the shape unite(0,1), unite(1,2), unite(2,3), … builds: a single path. find(0) then walks all n links. n operations can cost O(n²).

3. Union by size

The fix for tall trees is to choose which root goes under which: always hang the smaller tree (fewer elements) under the larger root.

std::size_t ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) std::swap(ra, rb);   // ra is the bigger tree
parent[rb] = ra;
size[ra] += size[rb];                         // only roots' sizes are kept up to date

Why that's enough to keep trees shallow: an element's depth grows by one only when its tree is hung under a tree at least as big, so the size of the tree containing it at least doubles. That can happen at most log₂ n times. Every tree has height ≤ log₂ n, and find is O(log n).

Union by rank is the same idea using an upper bound on height instead of the element count. Both work; size has the bonus of answering "how big is this group?" for free.

4. Path compression

find already walks from x to the root — so on the way back, point every node it passed directly at the root. The next find for any of them is one step.

std::size_t find(std::size_t x) {
    std::size_t root = x;
    while (parent[root] != root) root = parent[root];   // pass 1: locate the root
    while (parent[x] != root) {                          // pass 2: compress
        std::size_t next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

Two cheaper variants compress in a single pass while walking up:

• path halving: parent[x] = parent[parent[x]]; x = parent[x]; — every other node skips to its grandparent;
• path splitting: every node skips to its grandparent (with a temporary).

All three give the same guarantees.

How fast is "fast"?

With union by size and path compression, any sequence of m operations on n elements takes O(m · α(n)) time, where α is the inverse of the Ackermann function. α grows so slowly that α(n) ≤ 4 for any n that fits in the universe — call it constant. (The proof is famously intricate; the intuition is that compression keeps flattening exactly the paths you use, while union by size stops new long paths from forming.) Either technique alone gives O(log n) amortised.

5. Don't recurse

The textbook one-liner is tempting:

std::size_t find(std::size_t x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

It compresses correctly, but it uses one stack frame per link. Without union by size a chain can be a million links long, and the first find from its far end overflows the stack (8 MiB here, and debug builds use far bigger frames than you'd guess). The two-loop version uses O(1) stack whatever happens.

6. Counting components

Keep a counter that starts at n and drops by one each time unite actually merges. That's the number of sets at any moment — O(1), no scan.

7. Worked example: Kruskal's minimum spanning tree

A spanning tree connects all n vertices using n − 1 edges; a minimum spanning tree has the least total weight. Kruskal's algorithm: sort the edges by weight and take each one unless it would close a cycle — which is exactly "unless its endpoints are already connected".

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <optional>
#include <print>
#include <utility>
#include <vector>

class DisjointSet {
public:
    explicit DisjointSet(std::size_t n) : parent_(n), size_(n, 1) {
        std::iota(parent_.begin(), parent_.end(), std::size_t{0});
    }
    std::size_t find(std::size_t x) {
        std::size_t root = x;
        while (parent_[root] != root) root = parent_[root];
        while (parent_[x] != root) {
            std::size_t next = parent_[x];
            parent_[x] = root;
            x = next;
        }
        return root;
    }
    bool unite(std::size_t a, std::size_t b) {
        std::size_t ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size_[ra] < size_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        size_[ra] += size_[rb];
        return true;
    }

private:
    std::vector<std::size_t> parent_, size_;
};

struct Edge {
    std::size_t u, v;
    std::int64_t w;
};

std::optional<std::int64_t> mst_weight(std::size_t n, std::vector<Edge> edges) {
    std::ranges::sort(edges, {}, &Edge::w);
    DisjointSet ds(n);
    std::int64_t total = 0;
    std::size_t used = 0;
    for (const Edge& e : edges)
        if (ds.unite(e.u, e.v)) {   // joins two components: no cycle
            total += e.w;
            ++used;
        }
    if (n > 0 && used != n - 1) return std::nullopt;  // some vertex unreachable
    return total;
}

int main() {
    std::vector<Edge> roads{{0, 1, 4}, {1, 2, 2}, {0, 2, 5}, {2, 3, 7}, {1, 3, 3}};
    if (auto w = mst_weight(4, roads)) std::println("cheapest network: {}", *w);
}

Why is the greedy choice safe? Take any edge Kruskal accepts. Its endpoints are in different components, and it's the cheapest edge that crosses between them that we haven't rejected — the cut property says such an edge belongs to some minimum spanning tree. Union-find makes the cycle check nearly free, so the sort dominates: O(m log m).

8. Faded example: islands that appear one cell at a time

A grid starts as water; cells turn into land one by one, and after each change we want the number of islands (land connected through edges, not corners). Re-running a flood fill every time is O(cells) per step. With union-find each cell is an element:

// a new land cell is a new island...
++islands;
for (each of the 4 neighbours (nr, nc) inside the grid) {
    if (land[nr][nc] && /* ??? */) --islands;
}

Fill in the condition, and decide what happens when the same cell is added twice.

9. Where else it shows up

• Dynamic connectivity when edges are only added: network links, "are these two machines on the same cluster?".
• Equivalence classes: accounts sharing an email, synonyms in a dictionary, variables unified in a type checker.
• Percolation on grids, image segmentation, maze generation (unite cells by knocking down walls between different sets).
• Cycle detection in an undirected graph: an edge whose endpoints are already connected closes a cycle.

It can't handle deletions or "undo" directly, and it says nothing about paths or distances — for those, BFS, DFS and shortest-path algorithms (the other skills in this level) are the tools.

Summary

• One parent index per element; roots represent sets.
• unite: compare roots, hang the smaller tree under the larger, keep sizes on roots and a running component count.
• find: walk to the root with a loop, then compress the path.
• Together: O(α(n)) amortised — effectively constant.
• Kruskal = sort edges + union-find; n − 1 accepted edges means connected.