Union-Find

Disjoint Set Union

Pronunciation: YOON-yun FYND

Updated October 3, 20262 min read

In short

Union-find, or disjoint set union, is a data structure that tracks which elements share a group and can merge groups or check connectivity almost instantly.

What is union-find?

It supports two operations. find(x) returns a representative, the root, of the group that x belongs to, so two elements are in the same group exactly when their roots are equal. union(a, b) merges the groups of a and b by pointing one root at the other. Internally, each element just stores its parent, forming a forest of small trees.

Two simple tricks make it extremely fast. Path compression makes every element visited during find point directly at the root, flattening the tree. Union by rank or size always attaches the smaller tree under the larger one. Together they make each operation run in amortized time that grows so slowly, the inverse Ackermann function, that it is effectively constant for any real input.

Union-find shines whenever connections are added over time and you need to ask whether things are connected. Kruskal's algorithm uses it to build a minimum spanning tree, it counts connected components in a graph or a grid of islands, detects cycles as edges are added, groups duplicate accounts that share an email or phone number, and checks network connectivity.

A common misconception is that union-find can also split groups. It is designed for merging only; removing a connection or listing all members of a group efficiently needs a different structure. If connections can disappear, graph searches such as BFS or more advanced dynamic connectivity structures are required.

Key takeaways

Union-find tracks which elements belong to the same group.
find returns a group's root; union merges two groups.
Path compression and union by rank make operations nearly O(1).
Kruskal's algorithm, cycle detection and connected components use it.
It merges groups but cannot split them.

Example

Union-find with path compression and union by size (Python)python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression (halving)
            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 connected: this edge makes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                  # attach the smaller tree under the larger
        self.size[ra] += self.size[rb]
        return True

uf = UnionFind(5)
uf.union(0, 1); uf.union(3, 4)
print(uf.find(1) == uf.find(0), uf.find(1) == uf.find(3))   # True False

Readers ask

What is union-find used for?

Grouping elements and answering connectivity questions as connections are added: Kruskal's minimum spanning tree, cycle detection in undirected graphs, counting connected components, clustering and merging duplicate records.

What is path compression?

An optimization in find that makes each visited element point directly to the root, so later lookups on those elements are almost immediate.

What is the time complexity of union-find?

With path compression and union by rank or size, each operation takes amortized O(α(n)) time, where α is the inverse Ackermann function, which is at most 4 for any practical input size.