Union Find

Union Find

Union find, also called a disjoint set, tracks a collection of elements partitioned into non overlapping groups. It answers two questions extremely fast: which group an element belongs to, and whether two elements share a group.

The two operations

• Find returns a representative, the root, for an element's group by following parent pointers up a tree.
• Union merges two groups by pointing one group's root at the other's.

Two elements are connected exactly when their finds return the same root. This makes union find perfect for detecting cycles while building a graph and for Kruskal's minimum spanning tree.

The optimizations

Naively these trees can grow tall and slow. Two tricks keep them nearly flat:

• Path compression makes every node on a find point directly to the root, flattening the tree as you query.
• Union by rank always attaches the shorter tree under the taller one to avoid growth.

Together they bring each operation to nearly constant time, growing slower than any practical input size.

Key idea

Union find merges and queries disjoint groups in nearly constant time using path compression and union by rank.