Union-Find, in depth: disjoint sets, union by size, path compression and the inverse Ackermann bound

The representation: a forest of parent pointers

Number the elements 0 to n-1. Store one integer per element, parent[x]. Each group is a tree, and the root of the tree is the group's representative. A root points to itself. To find the representative of x, follow parent pointers until you reach a node that is its own parent. To merge two groups, find both roots and make one root the child of the other.

That is the entire data structure: one array, plus one more for the heuristics below. Nothing records a group's members or edges, which is why it is so compact, and also why it cannot answer questions like "which edge connected these two" or "split this group". It keeps only the partition, not the history that produced it.

parent = list(range(n))          # every element starts as its own root

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb          # arbitrary direction: this is what goes wrong

The naive code is correct but not fast. Union the elements in the order union(0,1), union(1,2), union(2,3) and so on, always linking the old root under the new element's root, and you build a single chain of length n. Every find on the deepest element then walks n steps, and n finds cost O(n squared). The two heuristics exist to stop trees getting tall, and to flatten them when they do.

Heuristic one: union by size or by rank

When merging two roots, hang the smaller tree under the larger one. With union by size you store the number of elements under each root; with union by rank you store an upper bound on the tree's height and attach the lower-rank root under the higher-rank one, incrementing the rank only when the two are equal.

Either rule guarantees height at most log2 n. The argument for size is short: an element's depth increases by one only when its tree is attached under a tree at least as large, so the size of the tree containing it at least doubles each time. Sizes cannot exceed n, so depth cannot exceed log2 n. That alone takes find from O(n) to O(log n) worst case.

Size is usually the better choice in practice because it is directly useful: size[find(x)] is the number of elements in x's group, a question applications ask constantly. Rank is equally good asymptotically and fits in a byte, which matters only for enormous arrays.

Heuristic two: path compression and path halving

Every find walks a path from x to the root. Path compression takes advantage of that walk: after finding the root, re-point every node on the path directly at it. Future finds on any of those nodes then take one step. The classic implementation is two passes, or one recursive function that assigns parent[x] = find(parent[x]) on the way back up.

Recursion is a real failure mode in Python and in threads with small stacks, because before compression kicks in, a path can be long. Path halving avoids both the recursion and the second pass: while walking, point each node at its grandparent and step to that grandparent. Path splitting is a close cousin that points every node on the path at its grandparent. Tarjan and van Leeuwen showed in 1984 that halving and splitting give the same asymptotic bound as full compression, so the one-pass iterative form is the default choice.

Compression alone, without union by size or rank, also gives O(log n) amortised per operation. The combination is what yields the famous bound.

How fast is it really? The inverse Ackermann bound

Tarjan proved in 1975 that with union by rank and path compression, any sequence of m operations on n elements takes O(m α(n)) time, where α is the inverse of the Ackermann function. The Ackermann function grows so fast that α(n) is at most 4 for any n that fits in the physical universe. Later work showed the bound is tight for this family of pointer-based structures: you cannot get to strictly constant amortised time this way.

Two practical caveats. First, the bound is amortised: an individual find can still walk a path of logarithmic length, which matters if you have a hard per-operation latency budget. Second, in real programs the cost is dominated by memory access, not by the step count. Dense ids and contiguous arrays matter more than choosing between rank and size.

Worked example: eight servers and their network links

Take eight servers numbered 0 to 7 and learn about direct network links one at a time: (0,1), (2,3), (1,3), (4,5), (6,7), (5,7), (3,7). After each link we want to know how many isolated clusters remain. Start with eight roots, each of size 1, and eight components.

Without any path shortening, the final tree has height 3, along the path 7, 6, 4, 0: exactly the log2 8 bound for eight elements. With the path halving used in the production code below, the two finds in the last step already re-pointed 3 at 0 and 7 at 4, so the height is 2 before anyone asks. If a later link (1,6) arrives, both finds return 0 and union returns False: the link is redundant, which in a graph means it closes a cycle. That one boolean is the basis of cycle detection and of Kruskal's algorithm.

Production code

The class below is what most systems need: iterative find with path halving, union by size, a live component count, and a union that reports whether anything changed. It uses plain Python lists; in a compiled language use a single int32 array per field.

class DisjointSet:
    # Union by size plus path halving. Iterative, so no recursion limit.
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        parent = self.parent
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving: skip a generation
            x = parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected: an edge here closes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                # smaller tree goes under the larger root
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

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

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

Real inputs rarely arrive as dense integers. When you are merging accounts by email, map each key to an id on first sight with a hash table, append a new root to parent and size for each new id, and after the unions group keys by find(id) in a single pass.

Where it is used

Kruskal's minimum spanning tree. Sort edges by weight and add each edge whose endpoints are not yet connected. The DSU is the connectivity oracle, and sorting dominates the running time.

def kruskal(n, edges):                 # edges: list of (weight, u, v)
    ds = DisjointSet(n)
    tree = []
    for w, u, v in sorted(edges):
        if ds.union(u, v):             # False means u and v are already joined
            tree.append((u, v, w))
            if len(tree) == n - 1:
                break
    return tree                        # fewer than n-1 edges: the graph is disconnected

• Cycle detection in undirected graphs. Process edges; the first union that returns False found a cycle. This does not work for directed graphs, where reachability is not symmetric.
• Offline connected components. For a static graph, BFS or DFS is just as fast. The DSU wins when edges arrive as a stream and you need answers between arrivals, or when you cannot hold adjacency lists in memory.
• Entity resolution. Records that share any identifier (email, phone, device id) belong to the same person. Union each record with each of its identifiers and read off the groups.
• Image segmentation and connected-component labelling. Union each pixel with matching neighbours in one raster scan.
• Percolation and clustering. Single-linkage clustering is Kruskal stopped early: stop when k components remain.

Variants worth knowing

Weighted or potential union-find. Store, for each node, a value relative to its parent: a parity bit, an offset, or a ratio. Find accumulates values along the path and compression must fold them into the re-pointed edge. This answers questions such as "is x an even distance from y" (bipartiteness checks) or "what is price(a) / price(b)" for currency-style constraints, and it detects contradictions when a union would join two already-connected nodes with an inconsistent value.

Rollback. Some algorithms need to undo the most recent unions, for example offline dynamic connectivity or backtracking search. Path compression rewrites many pointers per find and cannot be undone cheaply, so a rollback DSU uses union by size alone, accepts O(log n) finds, and records each union on a stack.

class RollbackDSU:
    # Union by size, NO path compression, so every union can be undone exactly.
    def __init__(self, n):
        self.parent = list(range(n)); self.size = [1] * n; self.history = []

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x                        # O(log n) worst case thanks to union by size

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            self.history.append(None); return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra; self.size[ra] += self.size[rb]
        self.history.append((ra, rb)); return True

    def rollback(self):
        op = self.history.pop()
        if op:
            ra, rb = op
            self.parent[rb] = rb; self.size[ra] -= self.size[rb]

Deletion is not supported. Removing an element or splitting a group requires knowing which edges hold it together, and the DSU threw that information away. If edges are deleted in arbitrary order, you need a fully dynamic connectivity structure or an offline algorithm; if you only need connectivity after deletions in bulk, rebuild. For richer questions about which edges are critical, see bridges and articulation points.

Concurrency. Lock-free variants built on compare-and-swap exist in the literature, but for most services a lock around the structure, or sharding the input, is simpler and fast enough.

Failure modes

Trade-offs against the alternatives

For a static graph you query once, BFS or DFS labelling is O(V + E) and gives you paths too; the DSU buys nothing. The DSU earns its place when unions and queries interleave, when the graph never needs to be materialised, or when you need a group's size in constant time. If you need deletions or path queries, reach for a different structure rather than bending this one.

What to do next

1. Implement the DisjointSet class above from memory, then test it against a brute-force BFS labelling on random graphs of a few thousand nodes.
2. Solve one entity-resolution problem, such as merging accounts that share an email, using the keyed wrapper.
3. Implement Kruskal's algorithm and check that the number of tree edges is n-1 on connected inputs and fewer on disconnected ones.
4. Add a parity field to make a weighted DSU and use it to test whether a graph is bipartite as edges arrive.
5. Benchmark path halving against full two-pass compression on 10 million random unions and note that memory layout, not step count, dominates.
6. Write down, for your own use case, whether you will ever need deletions; if yes, choose a dynamic connectivity approach before building on a DSU.