Union-Find

A connectivity query determines whether two nodes belong to the same connected component, even when they are linked through several intermediate nodes.

Running a graph search for every query is expensive. Union-find maintains component membership so these queries can be answered more efficiently.

Every item belongs to one set, and each set has a root that represents the whole group.

find(x) returns that root. union(a, b) merges the two sets. If find(a) and find(b) already agree, a and b are connected; otherwise union joins their groups.

The formal name is disjoint-set union, though most programmers call it union-find. It stores no edges and cannot reconstruct a path. It remembers only how the world is divided into non-overlapping groups.

That narrow scope is its strength. For connectivity under permanent merges, the structure makes both operations almost free.

In 1964 Bernard Galler and Michael Fischer described an improved algorithm for equivalence relations. Their representation is trees of parent pointers: each item points toward a root, and the root names the set.

A decade later Robert Tarjan proved the running time. With two small optimizations, m operations on n items run in O(m α(n)), where α is the inverse Ackermann function — a function that grows so slowly the difference from constant has never mattered in practice.

If a is equivalent to b, and b to c, then a is equivalent to c. Graph connectivity follows the same transitive rule.

Adding an edge merges two components. Later queries only need to know whether two vertices share one. As long as edges are added but never removed, union-find avoids traversing the graph again.

The representation is one parent pointer per item. At first, every item points to itself and forms a set of one.

To find a representative, follow parents until reaching a root that points to itself. To merge two sets, find their roots and point one at the other. One pointer write can join thousands of items.

Suppose 9 points to 4, 4 points to 2, and 2 points to itself. Then find(9) walks 9 → 4 → 2 and returns 2.

That root is the set’s representative. Every item that climbs to 2 belongs to the same set. Which item happens to be root does not matter; it is a stable answer shared by the whole component.

To union(9, 6), find the root of 9 and the root of 6. If both are already 2, nothing happens: they are connected.

If one root is 2 and the other is 8, point one root at the other. Everything that used to climb to 2 now climbs through 2 to 8. One parent pointer changes the representative of an entire component.

If every union attaches the first root below the second, some operation sequences produce a chain: 1 below 2, 2 below 3, 3 below 4, and so on.

In this case, find(1) traverses the entire chain and takes O(n) time. The optimization strategies therefore aim to keep parent-pointer trees shallow.

The first fix: when two roots merge, attach the shallower tree beneath the deeper one. Union by size — attaching the smaller beneath the larger — gives the same bound.

Chains can no longer form. A tree’s rank increases only when it absorbs a tree of equal rank, which at least doubles its size, so rank grows logarithmically in the number of nodes.

Path compression updates every node visited by find to point directly to the root.

The initial operation traverses the existing path. Later operations on those nodes reach the root with fewer pointer accesses.

Union-find can merge sets and test whether two items share a set. The standard structure cannot split a merged set.

Graphs that remove edges and may divide a component require a dynamic-connectivity structure instead.

With union by rank and path compression, m operations on n items take O(m α(n)) time, where α is the inverse Ackermann function.

For all practical input sizes, α(n) is at most 4. The amortized cost of each operation is therefore close to constant.

The implementation requires a parent array, a rank or size array, and the find and union operations. Find performs path compression, while union attaches the smaller or shallower tree below the larger one.

This compact implementation is suitable for problems that repeatedly merge groups and test component membership.

Kruskal’s minimum spanning tree algorithm sorts the edges by weight and scans them cheapest first.

For each edge, ask union-find whether its endpoints are already connected. If they are, the edge would close a cycle, so skip it. If not, keep the edge and union the components. Cycle detection becomes a pair of finds.

In a binary image, neighbouring foreground pixels belong to the same component. Scanning the image, union the provisional labels of adjacent pixels whenever they turn out to describe the same blob.

At the end every label compresses to its representative. Many provisional names collapse into connected components: letters on a page, islands in a mask, regions in a segmentation pass.

If one record shares an email address with a second record, and the second shares a phone number with a third, all three may represent the same entity.

Each match produces a union operation. After processing all matches, each root identifies one merged account or equivalence class.

Union-find records component membership but not the edges or paths that produced each component. It also does not support deletion in its standard form.

Rollback variants support some offline algorithms, while fully dynamic connectivity structures are required for general edge deletion.

Applications include network connectivity, percolation simulations, type unification, connected-component labelling, minimum spanning trees, clustering, and account merging.

These problems begin with separate items, merge related groups, and repeatedly test whether two items belong to the same group.

The first query may traverse several ancestors. Path compression updates those nodes to point at the root, reducing the work required by later queries.

Repeated queries therefore produce progressively shallower parent trees.

Union-find stores component membership as a forest of parent pointers. Union by rank limits tree height, and path compression shortens paths during queries.

The structure provides near-constant amortized time for permanent merges and connectivity tests, but it does not retain paths or support general component splitting.