Union Find

Track which items belong to the same group as edges arrive. With path compression and union by rank, find and union cost almost O(1) each.

Overview

What it is

Union Find, also called a disjoint set union (DSU), keeps a collection of groups that never overlap. It answers two questions fast: which group is x in (find), and merge the groups of x and y (union). It does not store the edges of a graph, only the groups they create, so it is the tool for questions about connectivity that do not need paths.

Each group is a tree. Every item points to a parent, and the root of the tree, which points to itself, is the group's name. Two items are in the same group when find reaches the same root for both. The whole structure is one array, parent, where parent[i] = i marks a root.

Union: link one root under the other

To merge the groups of x and y, find both roots. If they are the same, x and y are already connected and nothing changes. Otherwise make one root the parent of the other. Which root goes on top matters: always put the shorter tree under the taller one, so trees stay shallow. That is union by rank, where rank is an upper bound on the tree height. Union by size, which puts the smaller group under the larger, works just as well.

The trace below starts with six single items and applies six unions. A count of groups starts at 6 and drops by one on every union that actually merges.

(0, 1) — 0, 1 — equal rank: 1 under 0, rank of 0 becomes 1 — [0, 0, 2, 3, 4, 5] — [1, 0, 0, 0, 0, 0] — 5
(2, 3) — 2, 3 — equal rank: 3 under 2, rank of 2 becomes 1 — [0, 0, 2, 2, 4, 5] — [1, 0, 1, 0, 0, 0] — 4
(1, 3) — 0, 2 — equal rank: 2 under 0, rank of 0 becomes 2 — [0, 0, 0, 2, 4, 5] — [2, 0, 1, 0, 0, 0] — 3
(4, 5) — 4, 5 — equal rank: 5 under 4, rank of 4 becomes 1 — [0, 0, 0, 2, 4, 4] — [2, 0, 1, 0, 1, 0] — 2
(3, 5) — 0, 4 — rank 1 under rank 2: 4 under 0; find(3) also re-pointed 3 at 0 — [0, 0, 0, 0, 0, 4] — unchanged — 1
(0, 4) — 0, 0 — same root: no change, this edge closes a cycle — unchanged — unchanged — 1

The last row is the whole cycle-detection trick: an edge whose endpoints already share a root would create a cycle. The fifth row also shows path compression at work, which the next section explains: find(3) walked 3, 2, 0 and left 3 pointing straight at 0.

Find with path compression

find(x) walks parent pointers up to the root. Path compression makes every node on that walk point straight at the root, so the next find for any of them takes one step. The tree gets flatter every time it is used.

1 — 4 — 3 — not a root, keep walking
2 — 3 — 2 — keep walking
3 — 2 — 1 — keep walking
4 — 1 — 0 — keep walking
5 — 0 — 0 — root found
compress — 4, 3, 2, 1 — set each parent to 0

The iterative version does the walk twice, once to find the root and once to rewrite the pointers. The recursive version writes parent[x] = find(parent[x]) and is shorter, but recursion depth can reach the tree height on the first call.

Why the two optimizations matter

none — up to n - 1 — O(n) worst case — a chain forms when you always link the first root under the second
union by rank only — at most log2 n — O(log n) — a tree of rank r has at least 2^r nodes
path compression only — shrinks with use — O(log n) amortized is a safe bound — good on its own, but rank is cheap to add
both — almost flat — O(alpha(n)) amortized — alpha is the inverse Ackermann function

Tarjan showed in 1975 that with both optimizations a sequence of m operations on n items costs O(m alpha(m, n)). The inverse Ackermann function grows so slowly that it is 4 or less for any n you could store in a computer, so you may call each operation amortized constant time, and say why.

Union by rank alone gives log n because a root only gains rank when it absorbs a tree of equal rank, so a rank-r tree has at least 2^r nodes. Rank is never decreased by path compression, which is why rank is an upper bound on height rather than the exact height.

Counting groups and detecting cycles

Two questions come up more than any other. How many groups are there? Start at n and subtract one for every union that merges two different roots. Does this undirected graph have a cycle? Process the edges in order; the first edge whose endpoints already share a root closes a cycle. This is Redundant Connection: return that edge.

(1, 2) — 1, 2 — union — 2
(2, 3) — 1, 3 — union — 1
(3, 1) — 1, 1 — same root: this edge is redundant — 1

With m edges and n nodes the whole pass is O(m alpha(n)), and it needs no adjacency list.

Kruskal's minimum spanning tree

Sort the edges by weight and take each edge whose endpoints are in different groups. Union Find is the check. The taken edges form a tree of minimum total weight, and the sort dominates the cost at O(m log m).

A-B (1) — different — take — 1
B-C (2) — different — take — 3
A-C (3) — same — skip — 3
C-D (4) — different — take — 7
B-D (5) — same — skip — 7

Weighted Union Find: ratios along the path

Some problems attach a value to each relation, such as a / b = 2.0 and b / c = 3.0, then ask for a / c. Store, for each item, its ratio to its parent. When find walks to the root it multiplies the ratios along the way, and path compression stores the product so the item then points at the root with its ratio to the root.

To answer a / c: both have the same root, and the answer is weight(a) / weight(c) = 6 / 1 = 6. To union a and b given a / b = k, link root(a) under root(b) with weight k times weight(b) / weight(a), so the ratios stay consistent. Two items with different roots have no known ratio.

Union Find or BFS and DFS

Are x and y connected right now? — O(alpha(n)) per query after unions — O(n + m) per query, or precompute components once
Edges arrive one at a time — natural: union each edge as it comes — rebuild or re-run after each edge
Need the path, distance or order of visits — cannot: it only knows groups — yes
Directed graph — no: groups are undirected — yes
Remove an edge — no: groups cannot be split — re-run on the new graph
Memory — one or two arrays of size n — adjacency list plus visited set

Pick Union Find when the questions are only about membership in a group and the graph is undirected. Pick BFS or DFS when you need paths, directions or levels.

What you will be able to do

Write a DSU class with path compression and union by rank from memory, in Python, Java or JavaScript.
Trace unions and finds by hand, including the parent array after each step.
Explain why the two optimizations give almost constant time and what the inverse Ackermann function is.
Use it for components, cycle detection, Kruskal, account merging and ratio queries, and say when BFS or DFS is the better tool.

When to use it

Are two items connected, when edges arrive one at a time
Counting connected components in an undirected graph
Detecting the edge that closes a cycle in an undirected graph
Kruskal's minimum spanning tree: take an edge only if it joins two groups
Merging records that share an identifier, such as accounts that share an email
Grouping by an equivalence relation, including ratios or offsets between items

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio