Union-find: same root, same group

A building is being wired one cable at a time, each cable joining two computers. After every cable someone asks: can computer 3 now reach computer 8 through any chain of cables? Searching from 3 each time walks the cables laid so far, again and again.

It is really a question about groups. Computers that can reach each other form a group, and a new cable can only merge two groups, or do nothing if its ends already share one. Union-find tracks exactly that. It answers "same group?" and merges groups in nearly constant time, averaged over many operations, using just two arrays of numbers.

disjoint sets

Groups that share no elements, so every element is in exactly one set. Union-find is also called a disjoint-set structure.

parent and root

Each element stores one number, parent[x]. Following parents from any element ends at the root of its set, the one element that is its own parent. The root names the set.

find and connected

find(x) climbs parent links from x to the root and returns it. connected(a, b) asks whether find(a) and find(b) are the same root.

union

union(a, b) merges the set holding a with the set holding b: it finds both roots and makes one the parent of the other.

rank and path compression

Two tricks that keep trees flat. A root's rank is an upper bound on its tree's height, and union by rank hangs the root of lower rank under the other. Path compression points every element a find climbs past straight at the root.

Here are 8 elements, 0 to 7, each in a set of its own. Each set is drawn as a tree, root at the top, with an arrow from every element to its parent, above the arrays parent[x] and rank[x]. At the start every element is its own parent: all 8 are roots.

The sets live entirely in those links: two elements are connected exactly when their climbs reach the same root, and union points one root at the other. Neither tree is walked or copied: merging two sets of a million costs two finds and one link.

The cost to watch is the climb. A find follows one link per level, so it is as slow as the tree is tall. Suppose union always hung a's root under b's. Then union(0, 1), union(0, 2), union(0, 3) and so on would each hang the whole tree under one new element, building a chain: 0 under 1 under 2 under 3. With n elements, find(0) climbs n − 1 links: O(n).

Union by rank prevents that. Every root keeps a rank, an upper bound on its tree's height, and union hangs the root of lower rank under the other, so the merged tree keeps the larger rank and its height bound does not grow. Only a tie raises it: the new root's rank goes up by one (on a tie, this visualiser hangs b's root under a's). Rank 1 needs two elements and rank 2 needs two rank-1 trees, so at least four: a root of rank r has at least $2^r$ elements in its tree. So no tree is taller than log₂ n, which is 19 links for a million elements.

Path compression flattens the trees further, almost for free. A find climbs the whole path anyway, so once it knows the root it points every element it passed straight at it, and the next find from any of them takes one hop.

Two sets of five: 0 is the root of 0 to 4, with 3 under 2, and 5 is the root of 5 to 9, with 8 under 7, both of rank 2. Union 3 and 8, predicting at each step whether they already share a set, which root each find reaches, how many pointers compression changes and which root goes underneath. Then ask Connected? for 4 and 9.

In code, union-find is two lists of numbers. find_root (findRoot in JavaScript and TypeScript) is recursive, as in the recursion lesson: a root is the base case, and any other element gets its parent's root, stores it as its own parent and returns it. Those stores, made as the calls return, are path compression. (The visualiser makes them in a second loop instead.) union finds both roots, stops if they match, and otherwise hangs the lower-ranked root under the other.

The program starts from two sets: 0 is the root of 0 to 3, with 3 under 2, and 4 is the root of 4 and 5. The list is forest at the top and parent inside the functions, two names for one list. Each real merge returns 1, so groups counts the sets left.

def find_root(parent, x):
    if parent[x] != x:
        parent[x] = find_root(parent, parent[x])
    return parent[x]

def union(parent, rank, a, b):
    ra = find_root(parent, a)
    rb = find_root(parent, b)
    if ra == rb:
        return 0
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return 1

forest = [0, 0, 0, 2, 4, 4]
rank = [2, 0, 1, 0, 1, 0]
groups = 2
groups -= union(forest, rank, 3, 5)
print(groups)

The link goes between roots, and that matters more than it looks.

The classic user is Kruskal's algorithm for a minimum spanning tree, the cheapest set of edges connecting every node of a weighted graph. It takes edges cheapest first and keeps one only if its ends are not yet connected; otherwise it would close a cycle.

Counting a graph's connected components is the same loop: start with n sets, union the ends of every edge, and subtract one for each union that links two roots, as groups did. Either way, the check must compare roots, not parents.

How fast is it in the end? With both tricks, any m operations on n elements take O(m α(n)) time in total, where α, the inverse Ackermann function, is at most 4 for any n you could ever store. That is nearly constant per operation, but only on average over the sequence, and that caveat matters.

Union-find only merges, though: it has no operation that splits a set apart again.

• Union-find keeps disjoint sets as trees in one parent array. A root is its own parent and names its set.
• find climbs to the root, and connected(a, b) is find(a) = find(b): compare roots, never parents.
• union(a, b) links the two roots. Overwriting a non-root's parent splits its set instead.
• Union by rank keeps every tree at most log₂ n tall; path compression points each path a find climbs at the root.
• Together, m operations take O(m α(n)): nearly constant each, amortised. Sets merge but never split.
• Next: minimum spanning trees, where Kruskal's algorithm uses union-find to skip edges that would close a cycle. Practise with Count Connected Groups and The Extra Edge, or open the union-find visualiser to try more operations.