Union-Find (Disjoint Set) — Data Structures Course

What you'll learn

Union-Find (a disjoint-set structure) tracks a collection of non-overlapping sets and answers one question blazingly fast: are these two elements in the same set? With two small optimizations, each operation is effectively O(1).

By the end you'll be able to:

Use the two operations: find (which set?) and union (merge sets)
Apply union by rank and path compression
Explain its near-constant amortized cost

Disjoint sets

Represent each set as a tree, stored compactly in a parent array: parent[i] is i's parent, and a root points to itself. Two elements are in the same set exactly when they share the same root. union merges two sets by pointing one root at the other.

union & find

The parent array below is the whole structure. Watch a few unions build up sets, then a find with path compression flatten the tree:

Union-Find on a parent array

union / find with path compression

1/6Union-Find on 6 items. parent[i] = i means every element is the root of its own set — six singletons.

Each cell holds parent[i]; the index below is the element. Yellow = the find path · purple = a pointer that changed.

Two optimizations

Naively, trees can grow into long chains, making find slow. Two tricks keep them flat:

Union by rank (or size): always attach the shorter tree under the taller one, so the tree never gets needlessly deep.
Path compression: during find, re-point every node on the path directly to the root — so the next lookup is instant.

Key idea

With both optimizations, m operations on n elements take O(m · α(n)), where α is the inverse Ackermann function — under 5 for any conceivable input. In practice, that's constant time per operation.

In code

Language

unionfind.py

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each item is its own root
        self.rank = [0] * n            # tree height estimate

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already in the same set
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra            # attach the shorter tree
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Recap & quick check

Key takeaways

Union-Find maintains disjoint sets as trees in a parent array; a root points to itself.
find returns an element's root; two elements share a set iff they share a root.
union merges two sets by linking one root under the other.
Union by rank keeps trees shallow; path compression flattens them during find.
With both, operations are amortized O(α(n)) — effectively constant.

Quick check

1. In union-find, two elements are in the same set when they:

2. What does path compression do?

3. Union by rank attaches:

4. With both optimizations, each operation is amortized:

That completes graphs. All that's left is to tie it together and learn to pick the right tool. Next up: Module 30 — Amortized Analysis & Advanced Structures.