Union-Find (DSU)

Friend groups merge, network cables connect machines, pixels join into regions. Union-Find answers "are these two in the same group?" while groups keep merging, in practically constant time, and it is the engine inside Kruskal's algorithm.

intermediate⏱ 12 min read

←Builds on

5Trees: Concepts, Properties, TraversalsEach DSU group is a tree, and find walks up to its root.6Depth-First Search (DFS)DSU answers "connected?" like DFS on components, but stays fast while edges keep arriving.

Leads to→

8Minimum Spanning Tree: Kruskal & PrimKruskal asks "same component?" for every edge, which is DSU's find.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Two operations: find and union

A disjoint set union (DSU, Union-Find) keeps elements split into groups that never overlap. It supports just two operations:

find(x): which group is x in? It returns a representative, so find(a) == find(b) means "same group".
union(a, b): merge the groups of a and b.

You could relabel every member on each merge, but merging two big groups would then cost O(n). A graph search per question is even worse. DSU does both operations in almost O(1), with no way to split groups again (that is the price).

Typical uses: connected components while edges keep arriving, detecting a cycle when adding an edge, and Kruskal's minimum spanning tree, the next topic.

02A forest of parent pointers

Store one array, parent[]. Each group is a tree, every element points to its parent, and the root points to itself and names the group. Start with parent[i] = i: every element is its own tree of one element.

find(x): follow parent until parent[r] == r, return r.
union(a, b): find both roots; if they differ, make one root the parent of the other.

That is the whole data structure: a few lines and an array. In the picture, find(4) walks 4 → 3 → 1 and answers 1, so 4 and 2 are in the same group, while 6 (root 5) is not.

The only danger is the shape of the trees: find costs as much as the depth of the element.

03Keep trees flat: union by rank

If union always hangs the first root under the second, a bad order of unions builds a chain, and find at the bottom costs O(n).

Union by rank fixes it: keep a rank[] (an upper bound on tree height) for each root and always attach the lower tree under the higher one. Only when two ranks are equal does the new root's rank grow by 1. A tree of rank r then has at least 2ʳ elements, so heights stay O(log n).

Union by size (attach the smaller group under the larger) gives the same guarantee and is just as common; pick either one.

04Path compression, and the nearly constant bound

Second trick: when find(x) has walked up to the root, point every node on that path directly at the root. The next find from any of them takes one hop. In code it is a single line:

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

In the visualizer's run, find(8) walks 8 → 7 → 5 → 1 and afterwards 8, 7 and 5 all point at 1.

With both tricks, any sequence of m operations costs O(m · α(n)), where α is the inverse Ackermann function: it is at most 4 for any n you will ever store. In practice that is constant time per operation.

Cost at a glance

find / union (rank + compression)O(α(n)) amortized

Union by rank onlyO(log n)

No optimizations (worst case)O(n)

MemoryO(n)

Remember

DSU stores each group as a tree in a parent[] array; the root names the group.
Union by rank keeps trees shallow and path compression flattens them as you search.
Together they make find and union effectively O(1), which is exactly what Kruskal needs.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the rank row: it grows only when two roots of equal rank merge. At the end, see find(8) flatten its path.

Interactive visualizerfocus here, then space ← →

Disjoint Set Union (Union-Find)

i	1	2	3	4	5	6	7	8
parent[]	1	2	3	4	5	6	7	8
rank[]	0	0	0	0	0	0	0	0

Union-Find keeps elements split into disjoint sets, as a forest: each set is a tree, and its root names the set. At first every element is its own root.

Pseudocode

 1 each element starts as its own set (parent[i] = i) 2 find(x): follow parent[] up to the root 3 union(a,b): link the root of one under the other 4   attach the smaller-rank root under the larger  (union by rank) 5   equal ranks → pick one, its rank grows by 1 6 find(x) also flattens the path (path compression): 7   point every node on the path directly at the root

1 / 1

Check

Three questions. Pick an answer to see why.

Start with 1…4 separate. Run union(1,2), union(3,4), union(1,3) by rank; on equal ranks the root of the first argument becomes the parent. What is the root of 4?

What does path compression change?

Adding edge (u, v) to a graph: when does it close a cycle?

Practice

Real problems to lock it in, easiest first.

LeetCodeNumber of Provinces intermediate↗LeetCodeRedundant Connection intermediate↗CSESRoad Construction intermediate↗LeetCodeAccounts Merge intermediate↗