union–find #

Union–find, or the disjoint-set union structure, maintains a partition of a fixed universe into non-overlapping sets. It answers one question extremely well: are these two elements connected by the unions observed so far?

Its interface has three operations:

• makeSet(x) creates the singleton set {x};
• find(x) returns a representative for the set containing x;
• union(a, b) merges the two sets when their representatives differ.

Representatives are implementation identities, not meaningful members chosen by the caller. Equality of representatives is what proves connectivity.

a forest, flattened by use #

The standard representation is a forest of parent pointers. Every set is one tree; its root is the representative and points to itself, or stores a special root marker. find follows parents to a root. union changes one root's parent to the other root.

Before find, nodes seven, six, and four form a chain to root zero. After finding seven, all nodes on that path point directly to zero. before find(7)after find(7) 0 4 6 7 2 5 0 2 4 6 7 5 three parent reads reach the rootfuture finds take one parent read

A compact parent array often stores roots as negative set sizes:

parent[x] >= 0   → parent index
parent[x] < 0    → x is a root; -parent[x] is the set size

This combines parent pointers and rank metadata in one machine word per element. It requires elements to have dense integer identifiers, or a separate map from external keys to those identifiers.

weighted union #

A naive union can repeatedly attach a large tree beneath a singleton and create a linear chain. Union by size attaches the smaller root beneath the larger; union by rank attaches the shallower tree beneath the deeper one and raises the rank only when equal ranks meet.

union(a, b):
    ra = find(a)
    rb = find(b)
    if ra == rb: return false
    if size[ra] < size[rb]: swap(ra, rb)
    parent[rb] = ra
    size[ra] += size[rb]
    return true

Without path compression, weighted union keeps tree height logarithmic. With path compression, each successful or unsuccessful query also makes future queries cheaper.

path compression #

A full compression find first locates the root, then walks the path again and rewrites every parent:

find(x):
    root = x
    while parent[root] is not a root:
        root = parent[root]

    while x != root:
        next = parent[x]
        parent[x] = root
        x = next

    return root

Two one-pass relatives are common:

• path splitting makes every visited node point to its grandparent;
• path halving does this for every other node.

They can have simpler loops and excellent practical behavior. All preserve the same partition.

complexity #

A sequence of m operations on n elements using weighted union and path compression costs

O(m α(n))

where α is the inverse Ackermann function. It grows so slowly that it is below 5 for any practical input size. The useful interpretation is amortized almost constant time, not literally constant time: one particular find may still walk a path, and the bound applies across the operation sequence.

implementation	worst tree height	amortized operation cost
arbitrary linking	O(n)	O(n)
union by size/rank	O(log n)	O(log n)
size/rank + path compression	—	O(α(n))

Space is O(n).

what it does not maintain #

Union–find remembers connectivity, not the edges that established it. It cannot list a path between two elements unless another graph representation keeps the edges. It also does not efficiently support splitting a set or deleting an arbitrary union: one removed edge may or may not disconnect the component, and the parent forest contains too little information to decide.

For a changing graph, common choices are:

• process additions online and rebuild after deletions;
• answer an offline sequence in reverse, turning deletions into unions;
• use rollback union–find with a segment tree over time;
• use a fully dynamic connectivity structure when the added complexity is justified.

Path compression conflicts with simple rollback because one find mutates many parents. Rollback implementations usually omit compression, use union by size, and record each changed word on a stack.

applications #

• connected components in an incrementally built undirected graph;
• Kruskal's minimum-spanning-tree algorithm, rejecting edges whose endpoints already share a representative;
• percolation and image-component labeling;
• equivalence classes in compilers, type inference, and symbolic processing;
• offline connectivity and account/entity merging.

The fit is strongest when relationships only accumulate during the lifetime of the structure.

representation and correctness #

The fundamental invariant is that every parent chain terminates at exactly one root. Useful debug checks include:

• a root's stored size equals the number of elements that reach it;
• the sum of root sizes equals the universe size;
• non-root parents are valid indices;
• find(find(x)) == find(x);
• a successful union decreases the number of roots by exactly one.

Concurrency is not obtained by merely making parent words atomic. Two unions can race while choosing roots, lose a size update, or form a cycle. Concurrent variants need a defined linking order plus compare-and-swap loops, or a lock around mutations. Coarse locking is often the right first implementation because ordinary union–find operations are already very cheap.

sources #

• Bernard A. Galler and Michael J. Fisher, “An Improved Equivalence Algorithm,” Communications of the ACM 7(5), 1964, doi:10.1145/364099.364331.
• Robert Endre Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm,” Journal of the ACM 22(2), 1975, doi:10.1145/321879.321884.
• Robert E. Tarjan and Jan van Leeuwen, “Worst-Case Analysis of Set Union Algorithms,” Journal of the ACM 31(2), 1984, doi:10.1145/62.2160.

in these projects #

• Coral's lattice uses a negative-size parent array, weighted union, and full path compression to track connected occupied sites and detect percolation. Because expiring a site is a deletion, it periodically rebuilds the structure from live sites.