Union-Find (Disjoint Set Union)

The Data Structure

A Union-Find (Disjoint Set Union, DSU) data structure tracks a set of elements partitioned into disjoint (non-overlapping) subsets. It supports two operations in near-constant time:

• Find(x): determine which subset x belongs to (returns the representative of that subset).
• Union(x, y): merge the two subsets containing x and y into a single subset.

The classic application is tracking connected components in a graph as edges are added. Initially, each node is its own component (parent of itself). When an edge connects two nodes, we union their sets.

Union by Rank & Path Compression

Two optimizations make Union-Find nearly O(α(n)) per operation (inverse Ackermann — practically constant for any reasonable input):

• Path compression: during Find, flatten the tree by making each visited node point directly to the root. This keeps trees shallow.
• Union by rank: always attach the smaller tree under the root of the larger tree. The 'rank' is an upper bound on tree height.

Visualization

Consider 5 nodes initially: each node is its own component (self-loop parent). After unions: union(0,1), union(2,3), union(1,4):

After the unions, we have 3 components: {0,1,4} with root 0 (or 1, depending on rank), {2,3} with root 2, and {4} alone as its own component. Find(4) returns the root 0 after path compression.

When to Use

• Dynamic connectivity: track components as edges are added incrementally (cannot disconnect).
• Graph cycle detection in undirected graphs: if two nodes are already in the same set, the edge creates a cycle.
• Number of connected components: DSU tracks this naturally — count roots.
• Redundant connection problems: find the edge whose addition creates a cycle in a growing tree.
• Kruskal's MST algorithm: DSU is the core data structure for building a minimum spanning tree.
• Do NOT use when you need to support deletions or dynamic disconnection — use Link-Cut Tree or Euler Tour Tree instead.

Problems