Union-find¶

Keep track of which items belong to the same group while groups merge. Each group is a little tree; its root is the group's leader. Two items are together exactly when they have the same leader.

Union	Find (the leader)	Space
\(O(\alpha(n))\) amortized	\(O(\alpha(n))\) amortized	\(O(n)\)

\(\alpha(n)\) is the inverse Ackermann function, which is at most 4 for any \(n\) that fits in the universe: in practice, constant time.

The idea¶

Islands appear on a map one bridge at a time. After each new bridge, can you get from island 3 to island 7? Re-exploring the whole map after every bridge is slow. Union-find (also called a disjoint-set union) answers instantly.

Every item points to a parent; a leader points to itself. To find an item's leader, follow parents up to the root. To union two groups, find both leaders and make one point to the other.

Two small tricks make the trees almost flat:

Union by size: always hang the smaller tree under the larger one. Then any item's depth is at most \(\log_2 n\), because each time it gets deeper its group at least doubles.
Path compression: after a find, point every item on the path directly at the leader. Later finds on them take one step.

Together they give the astonishing \(O(\alpha(n))\) bound, proved by Tarjan in 1975.

How it works¶

find(x): walk up to the root; then walk the path again setting each parent to the root.
union(a, b): ra, rb = find(a), find(b); if equal, nothing to do; otherwise attach the smaller-size root under the larger and add the sizes.

Code¶

PythonJavaC++

class UnionFind:
    """Disjoint sets: which group is each item in? Union by size and path compression."""
    def __init__(self, n):
        self.parent = list(range(n))         # each item starts as its own group's leader
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:     # walk up to the leader
            root = self.parent[root]
        while self.parent[x] != root:        # path compression: point everything on the way at it
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Joins the groups of a and b; returns False if they were already together."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:    # hang the smaller tree under the bigger one
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


if __name__ == "__main__":
    uf = UnionFind(10)
    for a, b in [(0, 1), (2, 3), (1, 3), (5, 6), (7, 8), (8, 9), (3, 0)]:
        print(f"union({a}, {b}) -> {uf.union(a, b)}")
    print(uf.connected(0, 2), uf.connected(4, 5), uf.connected(7, 9))
    print("groups:", uf.groups, "size of 0's group:", uf.size[uf.find(0)])

public class UnionFind {
    final int[] parent, size;
    int groups;

    /** Disjoint sets: which group is each item in? Union by size and path compression. */
    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }   // each item leads its own group
        groups = n;
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];   // walk up to the leader
        while (parent[x] != root) {                   // path compression: point everything on the way at it
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    /** Joins the groups of a and b; returns false if they were already together. */
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }   // hang the smaller tree under the bigger
        parent[rb] = ra;
        size[ra] += size[rb];
        groups--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }

    static String py(boolean b) { return b ? "True" : "False"; }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        int[][] pairs = {{0, 1}, {2, 3}, {1, 3}, {5, 6}, {7, 8}, {8, 9}, {3, 0}};
        for (int[] p : pairs) System.out.println("union(" + p[0] + ", " + p[1] + ") -> " + py(uf.union(p[0], p[1])));
        System.out.println(py(uf.connected(0, 2)) + " " + py(uf.connected(4, 5)) + " " + py(uf.connected(7, 9)));
        System.out.println("groups: " + uf.groups + " size of 0's group: " + uf.size[uf.find(0)]);
    }
}

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

// Disjoint sets: which group is each item in? Union by size and path compression.
struct UnionFind {
    vector<int> parent, size;
    int groups;

    explicit UnionFind(int n) : parent(n), size(n, 1), groups(n) {
        iota(parent.begin(), parent.end(), 0);       // each item starts as its own group's leader
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];   // walk up to the leader
        while (parent[x] != root) {                  // path compression: point everything on the way at it
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    // Joins the groups of a and b; returns false if they were already together.
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) swap(ra, rb);       // hang the smaller tree under the bigger one
        parent[rb] = ra;
        size[ra] += size[rb];
        groups--;
        return true;
    }

    bool connected(int a, int b) { return find(a) == find(b); }
};

const char* py(bool b) { return b ? "True" : "False"; }

int main() {
    UnionFind uf(10);
    vector<pair<int, int>> pairs = {{0, 1}, {2, 3}, {1, 3}, {5, 6}, {7, 8}, {8, 9}, {3, 0}};
    for (auto [a, b] : pairs) cout << "union(" << a << ", " << b << ") -> " << py(uf.unite(a, b)) << "\n";
    cout << py(uf.connected(0, 2)) << " " << py(uf.connected(4, 5)) << " " << py(uf.connected(7, 9)) << "\n";
    cout << "groups: " << uf.groups << " size of 0's group: " << uf.size[uf.find(0)] << "\n";
}

Output: six unions succeed and union(3, 0) returns False (0 and 3 were already joined through 1); then True False True; then groups: 4 ({0,1,2,3}, {4}, {5,6}, {7,8,9}) and the size 4 of 0's group.

When to use it¶

Kruskal's minimum spanning tree: add the cheapest edge that joins two different groups.
Connected components of a graph whose edges arrive over time; counting islands; network connectivity.
Cycle detection in an undirected graph: an edge inside one group closes a cycle.
Grouping equal things: accounts that share an email, pixels of one colour region, variables that must be equal (type inference, unification).
It cannot split groups apart again; for deletions you need other structures.

Common mistakes¶

Comparing items instead of leaders: parent[a] == parent[b] is wrong; use find(a) == find(b).
Forgetting union by size or rank: with only path compression it is still fast in practice (\(O(\log n)\) amortized), but with neither, a chain can make every find \(O(n)\).
Recursive find on a deep chain can overflow the stack before compression flattens it; the loop version here is safe.
Updating the size of the wrong root after the swap.

Going deeper¶

Each part below starts closed; open the ones you want.

Sample walkthrough: the demo's unions on 10 items

Operation	Leaders found	Result (parent changes)	Groups
union(0, 1)	0, 1	1 → 0	9
union(2, 3)	2, 3	3 → 2	8
union(1, 3)	0, 2 (sizes 2, 2)	2 → 0	7
union(5, 6)	5, 6	6 → 5	6
union(7, 8)	7, 8	8 → 7	5
union(8, 9)	7, 9 (sizes 2, 1)	9 → 7	4
union(3, 0)	0, 0	already together: False	4

Finding 3's leader in the last step walks 3 → 2 → 0, then compression sets 3's parent to 0 directly.

The math: why the trees stay shallow

Union by size alone gives depth \(\le \log_2 n\). An item's depth grows by 1 only when its root is hung under another root whose tree is at least as big, so the size of the item's group at least doubles. A group can double at most \(\log_2 n\) times.

With path compression too, any sequence of \(m\) finds and unions on \(n\) items costs \(O(m\,\alpha(n))\) (Tarjan, 1975), and this is optimal for this kind of structure (Fredman and Saks, 1989). Here \(\alpha\) is the inverse of the very fast-growing Ackermann function \(A\):

\[ \alpha(n) = \min\{k : A(k, k) \ge n\}, \qquad A(4, 4) \gg 2^{2^{2^{65536}}}, \]

so \(\alpha(n) \le 4\) for every \(n\) we could ever store.

A simpler bound with path compression and union by rank is \(O(m \log^* n)\), where \(\log^* n\) is the number of times you must take \(\log_2\) to get down to 1: \(\log^* 2^{65536} = 5\).

Watch it step by step

Arrows point from an item to its parent. Blue is the new group's leader, red the root that was hung under it.

Variations and related ideas

Union by rank (an upper bound on height) instead of size: the same guarantees.
Path halving / splitting: point every node to its grandparent while walking up; one pass, same bound.
Weighted union-find stores, on each edge, an offset to the parent: it answers "how much heavier is \(a\) than \(b\)?" or checks parity constraints (is this graph bipartite?).
Offline dynamic connectivity handles deletions by processing queries in a clever order.

References¶

R. E. Tarjan, "Efficiency of a good but not linear set union algorithm", Journal of the ACM 22(2), 1975.
B. A. Galler, M. J. Fischer, "An improved equivalence algorithm", Communications of the ACM 7(5), 1964.
T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 19 (data structures for disjoint sets).