Union-Find

Links that only ever appear

Ten machines, numbered 0 to 9, sit on a network that grows one link at a time. The links arrive in this order: $(1,2),(3,4),(1,3),(5,6),(7,8),(5,7),(0,9),(1,5)$. No link is ever removed. After every new link, the operators ask questions like "can machine 2 talk to machine 8?", meaning: is there a path of links between them?

The answer for 2 and 8 is "no" after each of the first seven links and "yes" after the eighth, when link #8 joins the group $\{1,2,3,4\}$ to the group $\{5,6,7,8\}$.

The same shape of problem appears whenever "joined" only grows: Kruskal's algorithm for a minimum spanning tree, which adds edges and has to skip any edge whose ends are already connected; pixels merged into regions of an image; accounts merged because they share an address. This module needs two operations and asks how cheap they can be:

• union(a, b): merge the group containing $a$ with the group containing $b$;
• find(x): return a representative of $x$'s group, the same one for every member, so that $a$ and $b$ are connected exactly when find(a) == find(b).

The prerequisite is the definition of amortized cost from Amortized Analysis. The rest is self-contained.

The naive approach: search again

The obvious answer is to keep the links and search. To answer "can 2 talk to 8?", run a breadth-first search from 2 over the links so far and see whether it reaches 8.

from collections import deque

LINKS = [(1, 2), (3, 4), (1, 3), (5, 6), (7, 8), (5, 7), (0, 9), (1, 5)]

def reach(n, links, u):
    """Every machine a search from u reaches over the given links."""
    adj = [[] for _ in range(n)]
    for a, b in links:
        adj[a].append(b)
        adj[b].append(a)
    seen, queue = {u}, deque([u])
    while queue:
        x = queue.popleft()
        for y in adj[x]:
            if y not in seen:
                seen.add(y)
                queue.append(y)
    return seen

answers = [8 in reach(10, LINKS[:k], 2) for k in range(1, 9)]
visited = [len(reach(10, LINKS[:k], 2)) for k in range(1, 9)]
assert answers == [False] * 7 + [True]
assert visited == [2, 2, 4, 4, 4, 4, 4, 8] and sum(visited) == 32

Each search costs $\Theta (n+m)$ for $n$ machines and $m$ links, and it throws its work away. After link #3 the search from 2 discovers the group $\{1,2,3,4\}$. After link #4 it discovers that group again, although link #4 didn't touch it. With a million machines and a million links, a question after every link costs up to ${10}^6\times 2·{10}^6=2·{10}^{12}$ steps. The waste is exact: we only ever need to know which group a machine is in, never the path.

A second naive approach keeps a group label on every machine and, on each link, relabels one whole group. find is then one read, but a single union can relabel $n/2$ machines.

The model: a forest of parent pointers

Store each group as a rooted tree. Every machine has one pointer, parent[x]. A root points at itself and is the group's representative. find(x) follows parent pointers until it reaches a root, and union(a, b) finds both roots and makes one of them point at the other. Linking two roots merges exactly two whole groups. Linking a itself under b would cut a away from the rest of its own group.

The cost model in this module is pointer steps: the number of parent pointers find follows. A union costs two finds plus $O(1)$.

Without a rule for which root goes under which, the trees can be as bad as a list. Here is the rule-free version, run on the worst order: every new machine becomes the root above the chain built so far.

def find_steps(parent, x):
    """Walk to the root; return (root, pointer steps followed)."""
    steps = 0
    while parent[x] != x:
        x = parent[x]
        steps += 1
    return x, steps

def link_no_rule(parent, a, b):
    ra, rb = find_steps(parent, a)[0], find_steps(parent, b)[0]
    if ra != rb:
        parent[rb] = ra              # b's root always goes under a's root

n = 2000
parent = list(range(n))
for i in range(n - 1):
    link_no_rule(parent, i + 1, i)   # old chain goes under the new one
assert find_steps(parent, 0) == (n - 1, n - 1)
total = sum(find_steps(parent, 0)[1] for _ in range(n))
assert total == n * (n - 1) == 3_998_000

Machine 0 is at depth 1999, and 2000 questions about it cost 3,998,000 pointer steps. The fix takes two rules. Each is simple, and each attacks a different part of the cost.

Union by size

Rule 1: store at every root the size of its tree. On union, hang the root of the smaller tree under the root of the larger one, and add the sizes. On a tie, let a's root stay the root.

Here is the rule on the ten machines. After each link the figure shows the forest, with the size stored at each root:

Watch machine 8. It starts at depth 0. Link #5, $(7,8)$, hangs it under 7 (depth 1). Link #6, $(5,7)$, hangs 7's tree under 5 (depth 2). Link #8, $(1,5)$, hangs 5's tree under 1 (depth 3). Each time 8 went one level deeper, the tree it belonged to doubled: from 1 to 2, then 4, then 8 machines.

That observation is the whole proof. The block below checks it on the actual parent arrays. It does not rebuild them, which is the lab's job; it takes the arrays from the figure and verifies that every link obeyed the rule and that every depth respects the bound.

import math

# The parent array after each of the eight links, read off the figure.
FORESTS = [
    [0, 1, 1, 3, 4, 5, 6, 7, 8, 9], [0, 1, 1, 3, 3, 5, 6, 7, 8, 9],
    [0, 1, 1, 1, 3, 5, 6, 7, 8, 9], [0, 1, 1, 1, 3, 5, 5, 7, 8, 9],
    [0, 1, 1, 1, 3, 5, 5, 7, 7, 9], [0, 1, 1, 1, 3, 5, 5, 5, 7, 9],
    [0, 1, 1, 1, 3, 5, 5, 5, 7, 0], [0, 1, 1, 1, 3, 1, 5, 5, 7, 0],
]

def root(parent, x):
    return find_steps(parent, x)[0]

def tree_size(parent, r):
    return sum(root(parent, v) == r for v in range(len(parent)))

before = list(range(10))
for (a, b), after in zip(LINKS, FORESTS):
    ra, rb = root(before, a), root(before, b)
    if tree_size(before, rb) <= tree_size(before, ra):
        small, big = rb, ra                  # a tie keeps a's root
    else:
        small, big = ra, rb
    # exactly one pointer changed: the smaller root now points at the larger
    changed = [v for v in range(10) if before[v] != after[v]]
    assert changed == [small] and after[small] == big
    for v in range(10):                      # the depth lemma, in every forest
        size = tree_size(after, root(after, v))
        assert find_steps(after, v)[1] <= math.log2(size)
    before = after

groups = [sorted(reach(10, LINKS, v)) for v in range(10)]
for u in range(10):                          # same root exactly when connected
    for v in range(10):
        assert (root(before, u) == root(before, v)) == (v in groups[u])
assert find_steps(before, 8) == (1, 3) and tree_size(before, 1) == 8

Lemma. With union by size, every node has depth at most ${\log }_{2}n$.

Proof. A node's depth changes only when its root is hung under another root. Every other link leaves its path to the root untouched. The rule hangs a root under another only if the other tree is at least as large, so at that moment the tree containing our node goes from size $s$ to at least $2s$. The node starts in a tree of size 1, and no tree ever holds more than $n$ nodes, so its tree can double at most ${\log }_{2}n$ times. Its depth therefore goes up at most ${\log }_{2}n$ times. $◻$

The step to be careful with is which sizes are compared: the sizes of the two trees, stored at their roots, not the sizes or depths of the subtrees under a and b. A size read from a node that has stopped being a root is stale, and with it the doubling argument silently fails.

So find now costs at most ${\log }_{2}n$ pointer steps in the worst case, per call. The chain of 2000 becomes a tree of depth at most 10.

Path compression

Rule 2: once find(x) has walked up to the root $r$, walk the same path a second time and point every node on it straight at $r$.

In the last panel of the figure, find(8) follows 3 pointers ($8\to 7\to 5\to 1$), then re-points 8 and 7 at 1. (5 already points at 1.) The next find(8) follows 1 pointer. Nothing else changes: 4 and 6 keep their parents, because they were not on the path.

AFTER_FIND_8 = [0, 1, 1, 1, 3, 1, 5, 1, 1, 0]
assert [v for v in range(10) if AFTER_FIND_8[v] != FORESTS[-1][v]] == [7, 8]
# no group changed: every machine keeps its root
assert all(root(AFTER_FIND_8, v) == root(FORESTS[-1], v) for v in range(10))
assert find_steps(AFTER_FIND_8, 8) == (1, 1)

Compression never changes which nodes share a root, only how far they are from it. So it can be combined with either linking rule. It costs a second pass over a path the find already paid to walk, so it at most doubles the cost of the find that does it, and it makes later finds cheaper. Write it with loops. A recursive find on the 2000-long chain above would pass CPython's default recursion limit of 1000.

Both rules together: ${\log }^{*}n$ amortized

${\log }^{*}n$ ("log star") is the number of times you must apply ${\log }_2$ to $n$ before the result is at most 1. It grows absurdly slowly: ${\log }^{*}{2}^{65536}=5$, because $2^{65536}\to 65536\to 16\to 4\to 2\to 1$.

def log_star_of_power_of_two(e):
    """log* of 2**e, worked out on the exponent e."""
    count = 1                         # log2(2**e) = e
    while e > 1:
        e, count = math.log2(e), count + 1
    return count

assert log_star_of_power_of_two(16) == 4        # 65536 -> 16 -> 4 -> 2 -> 1
assert log_star_of_power_of_two(65536) == 5

Theorem (Hopcroft and Ullman, 1973). With union by size and path compression, any sequence of $m$ operations on $n$ elements costs $O((m+n){\log }^{*}n)$ pointer steps in total.

Here is the argument. It is a sketch: the ranks of nodes that are still roots keep growing, and that bookkeeping is skipped.

Ranks. When a node stops being a root, freeze its rank: $\lfloor {\log }_2\rfloor$ of the size of its tree at that moment. A root's rank is $\lfloor {\log }_2\rfloor$ of its current size.

Fact 1: ranks strictly increase toward the root. When $x$ is hung under $y$, $y$'s tree is at least as large as $x$'s, so the merged tree, and every later tree that $y$ roots, has at least twice $x$'s frozen size. Its rank is at least one more. Compression only ever gives $x$ a new parent that was higher on its path, so a higher rank still.

Fact 2: at most $n/2^r$ nodes have rank $r$. Picture the forest that the unions alone would build, with no compression. Compression changes no size, so it changes no rank, and in that forest a node's tree is fixed once the node stops being a root. Each node of rank $r$ heads a tree of at least $2^r$ nodes there: the tree it froze, or its current tree if it is still a root. Two nodes of the same rank head disjoint trees. If the trees overlapped, one node would lie inside the other's tree, below it, and by Fact 1 its rank would be lower.

Blocks. Group the ranks into blocks $\{0,1\},\{2\},\{3,4\},\{5,\dots ,16\},\{17,\dots ,65536\},\dots$, where each block ends at $2^t$ if the previous one ended at $t$. Ranks never exceed ${\log }_{2}n$, so there are at most ${\log }^{*}n+1$ blocks.

Charging. Each pointer step $x\to \text{parent}(x)$ of a find is paid for by one of two accounts:

• by the find, if the parent is the root or lies in a higher block than $x$. Ranks rise along the path, so this happens at most once per block boundary: at most ${\log }^{*}n+2$ times per find.
• by the node $x$, otherwise. Compression then gives $x$ a new parent of strictly higher rank. If $x$ is in the block that ends at $2^t$, then after at most $2^t$ such charges its parent is in a higher block, and $x$ is never charged again. By Fact 2, that block holds at most ${\sum }_{r>t}n/2^r=n/2^t$ nodes, so it absorbs at most $n$ charges in all. The first block, $\{0,1\}$, is the exception to that formula, and it is cheaper: a rank-1 node's parent already has rank at least 2, and a rank-0 node is charged only while its parent has rank 1, after which compression gives it a parent of rank at least 2. So this block also absorbs at most $n$ charges.

Summing: $m$ finds pay at most $m({\log }^{*}n+2)$, and the at most ${\log }^{*}n+1$ blocks pay at most $n$ each, so the total is $O((m+n){\log }^{*}n)$. $◻$

Theorem (Tarjan, 1975; stated, not proved). The same structure performs $m\ge n$ operations in $O(m\alpha (m,n))$ time, where $\alpha$ is an inverse of Ackermann's function. $\alpha$ grows far more slowly even than ${\log }^{*}$: it is at most 4 for any input that could ever be stored. Tarjan also showed that this analysis of the structure cannot be improved.

Lower bound (Fredman and Saks, 1989; stated). In the cell-probe model with cells of ${\log }_{2}n$ bits, every data structure for this problem, however it is built, needs $\Omega (m\alpha (m,n))$ time for $m$ finds and $n-1$ unions: for $m\ge n$, that is $\Omega (\alpha (m,n))$ amortized per operation. So union by size with path compression is optimal, not merely good.

The bounds side by side, all in pointer steps:

Space is $2n$ words, a parent and a size per element. Deletions are the one thing this structure can't do: a link that disappears can split a tree, and nothing in the forest records where. That needs a different structure.

Kruskal uses exactly this

Six sites with possible links $(w,u,v)$, weight first: $(4,0,1)$, $(8,0,2)$, $(2,1,2)$, $(6,1,3)$, $(3,2,3)$, $(9,2,4)$, $(5,3,4)$, $(7,3,5)$, $(1,4,5)$. Kruskal's algorithm sorts the links by weight and takes each one unless its ends are already connected. The cut property says the lightest link joining two different groups is always safe. "Already connected?" is one find per end, and taking a link is one union.

Here it takes $(1,4,5),(2,1,2),(3,2,3),(4,0,1),(5,3,4)$ for a total weight of 15. The next link, $(6,1,3)$, is the first one skipped, because 1 and 3 are already joined through 2 by the links of weight 2 and 3. Sorting costs $O(m\log m)$ and the finds $O(m\alpha (m,n))$, so the sort dominates. Relabelling the smaller group on each merge would also do here, at $O(n\log n)$ in total, since the sort dominates anyway. Union-find matters when the edges arrive already sorted or one at a time. It matters too when any two elements can be asked about: if the only question were "is this machine joined to machine 0?", a flag per machine, flooded outward once when its group first joins 0's, would cost $O(n+m)$ in total, because nothing ever loses the flag.

Measure the claim

A bound claims a growth rate, so count. These numbers come from a pointer-step counter on seeded random inputs at three sizes. For union by size alone it measures the deepest node after $2n$ random unions and the depth that the equal-size pairing input reaches. For both rules it measures the pointer steps per operation over $4n$ random operations, half unions and half finds:

The pairing column meets the lemma exactly, and random unions stay far below it. The last column is flat, which is consistent with the ${\log }^{*}n$ and $\alpha$ bounds. It is a measurement on these random inputs, not a proof: the theorems cover every sequence, including ones built to be expensive.

A problem that looks different

A sign-up system holds a million user records, and each lists one or more email addresses. Two records belong to the same person if they share an address, directly or through a chain of records that each share one with the next. How many distinct people are there? Nothing in the question mentions links or trees. The lab's last problem is a different one.

Practise

The lab has you write the linking rule and watch every depth stay under ${\log }_2$ of its tree's size, frame by frame. You then predict, and then write, path compression on a new sequence; build the whole structure and lay cable with Kruskal's algorithm on a new network; measure the depth bound, its tight input and the flat cost for yourself; and finally solve one problem that doesn't say what it is.

Recap

• You can now: keep a partition as a forest of parent pointers with find and union; prove that union by size keeps depth at most ${\log }_{2}n$ and build the input that reaches it; add path compression and sketch why the total cost becomes $O((m+n){\log }^{*}n)$; state Tarjan's $\alpha$ bound and the matching lower bound; and use the structure inside Kruskal.
• Invariant: two elements share a root exactly when they are in the same set, and under union by size a node gets deeper only when its tree at least doubles.
• Complexity achieved: at most ${\log }_{2}n$ pointer steps per find in the worst case with union by size, and $O(m\alpha (m,n))$ in total for any $m\ge n$ operations with both rules (amortized, not per find). Compare $\Theta (n)$ per find with no rule and $\Theta (n+m)$ per question when searching again.
• Failure mode: linking the arguments instead of their roots, or comparing sizes stored at nodes that are no longer roots.
• In real software: NetworkX's networkx.utils.UnionFind hangs the lighter root under the heavier and compresses paths, and its Kruskal routine for minimum_spanning_tree uses it to skip edges inside a component. SciPy's scipy.cluster.hierarchy.DisjointSet merges by size and shortens paths by path halving, a one-pass variant of compression.
• Retrieval: Amortized Analysis defined amortized cost. What exactly does an amortized $O(\alpha (m,n))$ bound promise about one find?

Check yourself

1. Why does union by size keep every depth at most ${\log }_{2}n$, and which input makes that bound exact?
2. Keep path compression but drop union by size. Give an order of unions that makes one find cost $n-1$ pointer steps. What does compression do to the finds after it?
3. Compare union by size with a label on every machine, where each link relabels the smaller group. What does each cost per find, and why do $n-1$ links cost the labels at most $n{\log }_{2}n$ relabellings in total?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.