Union-Find (Disjoint Set) Explained, with Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

What Is Union-Find?

Union-find, also called a disjoint set union (DSU), is a data structure that keeps track of a set of elements split into non-overlapping groups. Every element belongs to exactly one group, and each group is identified by a single representative, its root.

The trick is how the groups are stored: as a forest of trees. Each element holds a parent pointer, and following parents upward always leads to the group's root. Two elements are in the same group if and only if they share the same root. That is the whole idea, and everything else is about making it fast.

The Two Operations

Union-find supports exactly two operations, and its entire reputation rests on doing both almost instantly.

• find(x) returns the root of the group containing x, by walking up parent pointers. Two elements are connected when find(a) == find(b).
• union(a, b) merges the two groups by making one root the parent of the other.

Because groups only ever merge and never split, union-find is perfect for problems where connections are added over time but never removed.

The Naive Version and Its Problem

A first attempt just stores parent pointers and merges by pointing one root at the other. It works, but it has a nasty failure mode: nothing stops the trees from growing into long chains. If every union stacks one node on top of the last, find has to walk a chain of length n, and each operation degrades to O(n).

That is no better than a plain list. The fix is two small changes that, together, are one of the most celebrated results in data structures.

Two Optimizations That Change Everything

Union by rank keeps trees shallow. When merging two groups, always attach the shorter tree under the taller one's root. A short tree hanging off a tall one does not increase the height, so the trees stay flat.

Path compression flattens as it goes. Every time find walks up to a root, it re-points every node it passed directly at that root. The next find on any of them is then a single hop. The figure below shows one find collapsing a chain.

Used together, union by rank and path compression keep every tree almost completely flat, so both operations run in near-constant time. Either one alone helps; both together are what make union-find famous.

Implementation in Python

The full structure fits in a small class. Two arrays do all the work: parent and rank.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each element starts as its own root
        self.rank = [0] * n            # an upper bound on each tree's height

    def find(self, x):
        # Path compression: point x straight at the root.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already in the same group

        # Union by rank: hang the shorter tree under the taller.
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Notice that union returns False when the two elements were already connected. That single boolean is what makes cycle detection and Kruskal's algorithm so clean: if a union fails, the edge you were about to add would have closed a cycle.

Complexity: Almost Constant

With both optimizations, a sequence of m operations on n elements runs in O(m · α(n)) total, where α is the inverse Ackermann function.

The inverse Ackermann function grows so slowly that α(n) is at most 4 for any n that could fit in the observable universe. In practice, treat each operation as constant time. For how this sits among every graph algorithm, see the complexity guide and the cheat sheet.

Where It Is Used

Union-find shows up wherever you need to track connectivity as it grows.

• Kruskal's minimum spanning tree: sort the edges, then add each one only if its endpoints are in different groups. Union-find is the cycle check. See minimum spanning trees.
• Cycle detection in an undirected graph: for each edge, if both endpoints already share a root, the edge closes a cycle.
• Connected components: union every edge, then count the distinct roots.
• Dynamic connectivity and interviews: problems like Number of Provinces, Redundant Connection, and Accounts Merge are all union-find in disguise. See graph algorithms for coding interviews.

It also sits in Stage 3 of the graph theory study roadmap, right where you learn spanning trees.