What Is Union-Find?

Union-Find, or the Disjoint Set, is a structure that tracks which group each element belongs to and quickly answers whether two elements are connected, or merges two groups. It powers graph connectivity checks, Kruskal's MST, cycle detection, and grouping networks.

The one-line idea: "identify each group by a single representative (root)." Two elements are in the same group exactly when their representatives match.

Two Operations

•find(x): return the representative (root) of x's group by following parents upward until the root.
•union(a, b): find both representatives and hang one under the other to merge the groups.

Each element points to its parent in a parent[] array; an element whose parent is itself is a root.

The Core: Two Optimizations

A naive version can grow a tree into a long chain, making find O(n). Two optimizations make it near O(1):

•Path compression: while running find, reconnect every node passed directly to the root, so the next find finishes instantly.
•Union by rank/size: always attach the smaller (shorter) tree under the larger so height doesn't grow.

Used together, the average cost per operation is proportional to the inverse Ackermann function α(n) — effectively constant.

How It Works

Step 1. Init: parent[i] = i (every element is its own representative, a singleton group).

Step 2. find(x): climb upward while parent[x] != x to reach the root, and reconnect the nodes on the path directly to the root.

Step 3. union(a, b): ra = find(a), rb = find(b). If different, attach the lower-rank one under the higher (if equal, bump the merged side's rank by 1).

Step 4. Connectivity query: find(a) == find(b) means same set.

The AlgoNote visualization shows find's path to the root and how path compression flattens the tree, step by step.

Time and Space Complexity

Operation	Complexity
find / union	O(α(n)) ≈ O(1)
Space	O(n)

α(n) is the inverse Ackermann function — behaves like a constant ≤ 4 for any realistic input.

Walking Through an Example

Start with separate elements {0, 1, 2, 3}.

•union(0, 1) → 0 and 1 in one group
•union(2, 3) → 2 and 3 in one group
•union(1, 2) → the two groups merge into one {0,1,2,3}
•find(0) == find(3)? → yes (same representative)

Common Mistakes

•Skipping optimizations: dropping either path compression or union by rank can make the tree degrade to a chain.
•Comparing parents: don't test parent[a] == parent[b] — always use find to get roots and compare those.
•Initialization: not starting with parent[i] = i breaks root detection.

See It in Action on AlgoNote

Watch elements merge into groups and find locate the root while path compression flattens the tree, step by step on AlgoNote.

Try the Union-Find Visualization →