Union-find and disjoint sets

What this chapter covers

Union-Find is a tree used for something none of the other trees do: it tracks groups. Given a collection of elements, it maintains a partition into disjoint sets and answers two questions astonishingly fast — "merge the groups these two elements belong to" and "are these two in the same group?" There's no search, no ordering, no ranges; just grouping and membership. Its genius is in two tiny optimizations that, together, drop both operations to effectively constant time — so close to O(1) that the exact bound involves a function, the inverse Ackermann, that never exceeds 4 for any input you could physically store. This chapter builds it, watches groups merge and paths compress, and closes the tree tier with a structure that proves a tree can be a tool for connectivity, not just lookup.

A bit of history

Union-Find was introduced by Bernard Galler and Michael Fischer in 1964, as a way to manage equivalence classes — sets of things declared to be "the same" — which came up in compilers handling EQUIVALENCE declarations in Fortran. The basic structure was simple; what made it legendary was its analysis. Through the late 1960s and 70s, the two optimizations (union by rank and path compression) were added, and in 1975 Robert Tarjan proved the astonishing result: with both, a sequence of m operations on n elements runs in O(m·α(n)) time, where α is the inverse of the Ackermann function — a function that grows so unimaginably slowly that α(n) is at most 4 for any n up to the number of atoms in the universe. Tarjan later proved this bound is optimal — no pointer-based structure can do better. So union-find is that rare thing: a structure with a provably near-constant, provably optimal running time, discovered for a mundane compiler problem and now essential to graph algorithms.

The intuition

Represent each group as a tree, where every element points to a parent and the tree's root is the group's name (its "representative"). At the start, every element is its own root — n groups of one. To test whether two elements are in the same group, walk each up to its root and check whether the roots match: same root, same group. To merge two groups, find their two roots and make one point at the other — a single pointer change joins two entire trees.

Done naively, those trees can grow into long chains, and walking to the root becomes O(n). Two fixes keep them flat. Union by rank: when merging, always hang the shorter tree under the taller one, never the reverse, so the height barely grows. Path compression: every time you walk from a node up to the root, repoint that node — and every node on the path — directly at the root, so the next find is instant. Union by rank keeps trees from getting tall; path compression flattens whatever height remains as a side effect of just using the structure. Together they make the trees so flat that the amortized cost per operation is the inverse Ackermann function — a constant for all practical purposes.

Complexity: how it scales

With both optimizations, union, find, and connected are $O(\alpha(n))$ amortized — inverse Ackermann, which is at most 4 for any conceivable n, so treat it as constant. Building n singletons is $O(n)$, and space is $O(n)$ (a parent array and a rank array). The chart contrasts the real union-find against the naive version, whose union relabels an entire set in O(n) and so is O(n²) to build up:

At 16000 elements, the optimized union-find ran n unions plus n connectivity queries in about 6.6 ms; the naive version took 3754 ms — 566 times slower, because each of its unions swept the whole array. The optimized line is essentially flat (near-linear total, near-constant per operation) while the naive one climbs quadratically. That gap is the entire value of the two optimizations: they turn a structure that's unusable at scale into one of the fastest algorithms known.

What it's good at, what it isn't

Union-Find is the perfect and essentially only tool for incremental connectivity: you keep merging groups and asking whether things are connected, and you want both to be free. It's the engine of Kruskal's minimum spanning tree (add the cheapest edge that doesn't form a cycle — "doesn't form a cycle" is a union-find query), of finding connected components in a graph, of detecting cycles as you build one, and of any "are these two things in the same cluster/network/ equivalence class?" question. Whenever grouping is dynamic and you never need to look inside a group in order, union-find is unbeatable.

Its limitation is the flip side of its speed: it can only merge, never split. There's no efficient "un-union" — once two groups join, the structure has no cheap way to separate them, because path compression has scrambled the original tree shape. It also doesn't enumerate a group's members, or keep them ordered, or support anything but "same group?" — it's a connectivity oracle, not a container. If you need to remove connections (dynamic connectivity with deletions), that's a much harder problem requiring entirely different structures. Union- Find answers exactly one kind of question, and answers it as fast as anything can.

The data, or the inputs

The face-off performs n random unions and n connectivity queries at growing sizes, exposing the naive version's O(n)-per-union cost against the optimized near-constant one. The animation uses eight elements: it merges them into one group step by step, showing union by rank keeping the trees short, and then runs a find that path-compresses a node straight to the root.

Build it, one function at a time

Find walks to the root and compresses the path on the way — the operation everything rests on:

def find(self, x, probe=None):
    """O(α(n)) amortized: follow parent pointers to the root — the representative of
    x's set. PATH COMPRESSION: on the way back, repoint every node on the path
    directly at the root, so the tree flattens and future finds are nearly instant."""
    root = x
    while self._parent[root] != root:
        root = self._parent[root]
    while self._parent[x] != root:      # compress the path
        self._parent[x], x = root, self._parent[x]
    if probe is not None:
        probe.append(root)
    return root

Union finds both roots and attaches the shorter tree under the taller by rank:

def union(self, a, b):
    """Merge the sets of a and b. UNION BY RANK: attach the shorter tree under the
    taller one so the result stays shallow — never let a tall tree hang off a short
    one. Returns False if they were already in the same set."""
    ra, rb = self.find(a), self.find(b)
    if ra == rb:
        return False
    if self._rank[ra] < self._rank[rb]:
        ra, rb = rb, ra
    self._parent[rb] = ra
    if self._rank[ra] == self._rank[rb]:
        self._rank[ra] += 1
    self._count -= 1
    return True

Watch it work

Here are eight elements, each starting as its own group. Orange marks the elements being touched; blue marks a root (a group's representative). Step through it: unions merge pairs, then merge the pairs into fours, attaching the shorter tree under the taller so nothing gets tall. Then watch the finale — a find on element 7 walks up to the root, and path compression repoints it (and its path) directly at the root, flattening the tree so the next find is a single hop. That flattening, happening automatically on every find, is why the amortized cost is near-constant: the structure heals itself as you use it:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the optimized union-find. The library tab is the naive version — each element carrying a set id, union relabeling the whole set — kept so you can see that the entire 566× difference comes from representing sets as trees and applying two small optimizations. (Python has no built-in union-find; SciPy provides one for graph work.)

"""Union-Find (the disjoint-set union, or DSU) — a tree used not for searching but for
GROUPING. It tracks a partition of elements into disjoint sets and answers two questions
blazingly fast: "merge the groups containing these two elements" (union) and "are these
two in the same group?" (find/connected).

Each set is a tree whose root names the group; two elements are in the same set exactly
when they share a root. Two optimizations — union by rank (attach the shorter tree under
the taller) and path compression (on every find, point nodes straight at the root) — make
both operations effectively constant time: O(α(n)), where α is the inverse Ackermann
function, which is at most 4 for any n you could ever store. It's the structure behind
Kruskal's minimum spanning tree, connected components, and network connectivity.
"""


class UnionFind:
    def __init__(self, n):
        self._parent = list(range(n))       # each element starts as its own root
        self._rank = [0] * n                # upper bound on a tree's height
        self._count = n                     # number of disjoint sets

    # region: find
    def find(self, x, probe=None):
        """O(α(n)) amortized: follow parent pointers to the root — the representative of
        x's set. PATH COMPRESSION: on the way back, repoint every node on the path
        directly at the root, so the tree flattens and future finds are nearly instant."""
        root = x
        while self._parent[root] != root:
            root = self._parent[root]
        while self._parent[x] != root:      # compress the path
            self._parent[x], x = root, self._parent[x]
        if probe is not None:
            probe.append(root)
        return root
    # endregion

    # region: union
    def union(self, a, b):
        """Merge the sets of a and b. UNION BY RANK: attach the shorter tree under the
        taller one so the result stays shallow — never let a tall tree hang off a short
        one. Returns False if they were already in the same set."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self._rank[ra] < self._rank[rb]:
            ra, rb = rb, ra
        self._parent[rb] = ra
        if self._rank[ra] == self._rank[rb]:
            self._rank[ra] += 1
        self._count -= 1
        return True
    # endregion

    def connected(self, a, b):
        """Same group? Just compare roots — O(α(n))."""
        return self.find(a) == self.find(b)

    def count(self):
        return self._count

"""There's no union-find in the Python standard library (SciPy has one for graph
connectivity). The instructive counterpart is the NAIVE version — the one before the
optimizations — where each element just carries a set id and a union relabels an entire
set. That's O(n) per union, O(n²) to build up, which is exactly what union by rank and path
compression collapse to near-constant. The face-off shows that gap.
"""


# region: naive
class NaiveUnionFind:
    """Each element stores its set id; union relabels every member of one set — O(n) per
    union. Simple and correct, but quadratic to build, which is why the real union-find
    uses trees with path compression instead."""

    def __init__(self, n):
        self._id = list(range(n))
        self._count = n

    def find(self, x):
        return self._id[x]

    def union(self, a, b):
        ia, ib = self._id[a], self._id[b]
        if ia == ib:
            return False
        for i in range(len(self._id)):      # O(n): relabel the whole set
            if self._id[i] == ib:
                self._id[i] = ia
        self._count -= 1
        return True

    def connected(self, a, b):
        return self._id[a] == self._id[b]
# endregion

Scratch vs library

The 566× speedup is the whole story, and it's a pure algorithms story — same language, same problem, two ideas. The naive version isn't badly written; it's just fundamentally O(n) per union, and O(n) per operation over n operations is O(n²), which loses to near-linear by exactly the margin you'd predict. What makes union-find remarkable is how little separates the fast version from the slow one: union by rank is a two-line comparison, path compression is a two-line loop, and together they take an O(n²) structure to O(n·α(n)) — the best any structure of its kind can achieve. It's the clearest demonstration in the book that algorithmic improvements, not faster hardware or lower-level code, are where the orders of magnitude live: a few well-chosen lines beat a 566× hardware speedup you'll never get.

Where you'll actually meet it

Union-Find is everywhere connectivity is dynamic. Kruskal's minimum-spanning-tree algorithm (a graph chapter ahead) is built on it — it adds edges cheapest-first, using a union-find query to skip any edge that would form a cycle. Finding the connected components of a graph, or the number of distinct groups in a network, is a sweep of unions. Image processing uses it to label connected regions of pixels. Type inference and unification in compilers use it for equivalence classes (its original purpose). Physics simulations use it for percolation and clustering. Maze generation, Kruskal-style, uses it. And any "are these two accounts / servers / friends in the same connected group?" question at scale is a union-find lookup. It's a small structure with an enormous footprint in real algorithms.

Takeaways

Union-Find represents disjoint sets as trees named by their roots, and with union by rank and path compression it merges groups and tests membership in $O(\alpha(n))$ amortized time — effectively constant, and provably optimal. It's the tool for incremental connectivity and grouping: fast at merging and "same group?", but unable to split groups apart or look inside them. Two tiny optimizations take it from O(n²) to near-linear, the book's sharpest lesson that the big wins are algorithmic.

That completes the tree tier — from traversals and search trees, through balanced trees and heaps, to the specialized tries, range-query trees, disk-oriented B-trees, and this grouping structure. The next tier changes the shape of the problem entirely. Graphs generalize trees by dropping the "one parent, no cycles" rule: any node can connect to any other, forming networks — roads, social links, dependencies, the web. Most of what you've built reappears there as machinery (queues drive breadth-first search, heaps drive Dijkstra, union-find drives Kruskal), but the questions become richer: shortest paths, reachability, ordering, spanning trees. It begins with how you represent a graph at all.