Union-Find, also called the Disjoint Set Union (DSU), is a data structure that tracks a collection of elements partitioned into disjoint groups. It supports two operations: find(x), which returns a representative 'leader' of x's group, and union(a, b), which merges the two groups containing a and b. Two elements are in the same group exactly when they share a leader.

What are union by rank and path compression?

They are the two optimizations that make Union-Find fast. Union by rank always attaches the shorter tree under the taller one, keeping trees shallow. Path compression re-points every node visited during a find directly at the root, so future finds on those nodes are instant. Together they give near-constant amortized time per operation.

What is the time complexity of Union-Find?

With both union by rank and path compression, a sequence of m operations on n elements runs in O(m · α(n)) time, where α is the inverse Ackermann function. α(n) is less than 5 for any n that could ever be stored, so each operation is effectively constant time.

What is Union-Find used for?

It is the standard tool for connectivity questions: counting connected components in a graph, detecting cycles while building a graph, Kruskal's minimum spanning tree algorithm, grouping equivalent items, image segmentation, and 'are these two accounts in the same network' checks.

How does Union-Find detect a cycle?

While adding edges one at a time, call union(a, b) for each edge. If find(a) already equals find(b) before the union, then a and b were already connected, so adding this edge closes a cycle. This is exactly how Kruskal's algorithm avoids creating cycles in a minimum spanning tree.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 09 / UNION-FIND

Six Degrees.

Nine people, no friendships yet. Wire them up one handshake at a time and watch separate circles merge into one — then ask "same group?" and get the answer in near-constant time.

THE GIST · 20 SECONDS

Union-Find (the Disjoint Set Union) keeps a pile of things split into groups and answers one question fast: are these two in the same group? Each group elects a leader. find(x) walks up to x's leader; union(a, b) points one leader at the other, fusing two groups into one. With union by rank and path compression, every operation is effectively O(α(n)) — constant.

Seta group of connected items
Leaderthe root that names a group
unionmerge two groups into one
findwho leads my group?

Hit Step to make the next connection — or Play and watch the circles merge. Click any node to run find.

UNDER THE HOOD

What you just played, written down

Every group is a little tree. The root is the leader. Union points one root at another; find walks up to the root. Two tricks keep the trees almost flat.

How Union-Find thinks — four moves

Everyone is their own leader. Start with n singletons: parent[i] = i.
find(x): walk up to the root. Follow parent pointers until a node points to itself — that node is the group's leader.
union(a, b): join two roots. Find both leaders. If they differ, point one at the other — two groups become one.
Same group? Just check find(a) == find(b). Equal leaders means already connected.

THE CYCLE TRICK

If find(a) already equals find(b) before a union, that edge would close a cycle — the two were already connected. That single check is how Kruskal's MST rejects redundant edges.

The two speed-ups

parent = [0, 1, 2, ..., n-1]   # everyone leads itself
rank   = [0, 0, 0, ...]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # PATH COMPRESSION
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False          # already connected
    if rank[ra] < rank[rb]:            # UNION BY RANK
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]: rank[ra] += 1
    return True

TIMEO(α(n))amortized, per op

SPACEO(n)parent + rank arrays

WHY α(n) IS BASICALLY CONSTANT

Union by rank keeps trees shallow; path compression flattens them further on every find. Together the cost is the inverse Ackermann function — under 5 for any n in this universe.

⚠ Only rank-comparison, not exact height

After path compression, rank is only an upper bound on a tree's height, not its true height. That's fine — it's still enough to keep unions balanced.

↔ Its cousins

Union by size (attach the smaller group under the larger) works just as well as rank. Weighted quick-union is the same idea. For dynamic disconnection you need a different structure entirely.

★ Where it's used

Kruskal's MST, counting connected components, cycle detection, image segmentation, grouping equivalences, and "are these two accounts in one network?" checks.

The picture: groups are trees stored in one array

The state after eight unions on nine elements (before the find(7) in the table below). Each group is a tree and the highlighted node is its leader: 0 leads the eight-element group, 8 is still alone. The entire structure is the array underneath, where a root is the entry that points at itself. Node 7 is three hops from its root, which is exactly the kind of path compression will shorten.

Worked example, step by step

Nine elements, 0 to 8, all starting alone. Apply union(0,1), union(2,3), union(0,2), union(4,5), union(6,7), union(4,6), union(1,3), union(0,4), then find(7), using union by rank with path compression. Ties attach the second root under the first.

#	Operation	Result	parent after	rank after	Groups
1	union(0, 1)	merged	[0, 0, 2, 3, 4, 5, 6, 7, 8]	[1, 0, 0, 0, 0, 0, 0, 0, 0]	8
2	union(2, 3)	merged	[0, 0, 2, 2, 4, 5, 6, 7, 8]	[1, 0, 1, 0, 0, 0, 0, 0, 0]	7
3	union(0, 2)	merged	[0, 0, 0, 2, 4, 5, 6, 7, 8]	[2, 0, 1, 0, 0, 0, 0, 0, 0]	6
4	union(4, 5)	merged	[0, 0, 0, 2, 4, 4, 6, 7, 8]	[2, 0, 1, 0, 1, 0, 0, 0, 0]	5
5	union(6, 7)	merged	[0, 0, 0, 2, 4, 4, 6, 6, 8]	[2, 0, 1, 0, 1, 0, 1, 0, 0]	4
6	union(4, 6)	merged	[0, 0, 0, 2, 4, 4, 4, 6, 8]	[2, 0, 1, 0, 2, 0, 1, 0, 0]	3
7	union(1, 3)	already connected	[0, 0, 0, 0, 4, 4, 4, 6, 8]	[2, 0, 1, 0, 2, 0, 1, 0, 0]	3
8	union(0, 4)	merged	[0, 0, 0, 0, 0, 4, 4, 6, 8]	[3, 0, 1, 0, 2, 0, 1, 0, 0]	2
9	find(7)	walk 7 → 6 → 4 → 0, then flatten	[0, 0, 0, 0, 0, 4, 0, 0, 8]	[3, 0, 1, 0, 2, 0, 1, 0, 0]	2

Step 7 is the one to study: union(1, 3) returned “already connected”, because 1 and 3 were put in the same group at step 3 through the 0–2 link. The number of groups did not change, and this is the cycle check that Kruskal’s algorithm uses to reject an edge. Notice also that parent[3] changed from 2 to 0 at step 7 even though no merge happened: the find inside the failed union flattened the path as a side effect. Rank only grows when two roots of equal rank meet. At step 8 two rank-2 trees merged and the leader's rank became 3, and that root now has 8 elements, matching the rule that a root of rank r has at least 2^r. At the end, find(7) walked 7 → 6 → 4 → 0 and pointed 7 and 6 straight at 0 (4 already was), so the next lookup of 7 takes one hop. Two groups remain: {0…7} and {8}.

Complexity and trade-offs

Case	Time	Space	Why
Rank + path compression	`O(α(n))` amortized per operation	`O(n)`	α is the inverse Ackermann function, below 5 for any input that fits in memory, so it behaves like a constant.
Union by rank only	`O(log n)` per operation	`O(n)`	Trees can still reach height log₂ n, but not more.
Path compression only	`O(log n)` amortized	`O(n)`	No height bound for a single find, but the amortized cost stays logarithmic.
Neither heuristic	`O(n)` worst case per find	`O(n)`	Links can form a chain; one find may walk every element.
Recompute components by DFS after each edge	`O(m · (n + m))` total	`O(n + m)`	Correct, but redoes the whole graph for each new edge.

Measured on these inputs: linking 1000 elements as 0→1, 1→2, … without rank builds a chain of depth 999, so find(0) takes 999 hops. Running find on every element of that chain in order costs 499,500 hops without compression and 1,997 with it. Union by rank on 1024 elements merged pairwise, which is its worst case, tops out at depth 10 (log₂ 1024). The trade-off is what the structure cannot do: it only merges. It answers “are these connected?” in near-constant time, but it cannot split a group back apart, list a group's members cheaply, or tell you the path between two members. If edges are deleted, you need an offline approach or a rollback variant that undoes unions.

Common mistakes

Comparing parents instead of roots
parent[a] == parent[b] is not the test. After union(0,1), union(2,3), union(0,2), element 1 has parent 0 and element 3 has parent 2, so the parents differ, yet they are in one group. Always compare find(a) == find(b).
Linking elements instead of roots
Writing parent[a] = b without finding the roots detaches a from its group. After union(0,1) then union(0,2) done this way, find(0) is 2, but find(1) is still 1: element 1 has been left behind.
Decrementing the group count on every call
A redundant union must not change the count. For the edges (0,1), (1,2), (0,2) on nine elements, decrementing every time gives 6 groups; the correct answer is 7, because the third edge closed a cycle. Only decrement when find returned two different roots.
Reading parent[] as the group id
Unflattened, the array holds parents, not leaders. After (0,1), (2,3), (0,2), (4,5), (4,6), the entries of parent contain 5 distinct values, but there are 4 groups on those nine elements (counting 7 and 8 alone). Label with find(i) for each i.
Recursive find on a deep tree
A recursive find is fine with union by rank, but without it a chain of 5000 nodes raises RecursionError in Python at the default limit. Use an iterative find that does a second pass to compress, or keep the rank heuristic.

Where this shows up

Minimum spanning trees
Kruskal’s algorithm sorts the edges and adds each one only if its endpoints are in different groups, which is the “already connected” check from step 7.
Grid and image labelling
Scanning a binary image and unioning each pixel with its set neighbours labels every connected blob in one pass. The same pattern counts islands and detects when a percolation grid first connects top to bottom.
Merging records
Accounts that share an email, or items that share any attribute, form groups under transitive equality. Union each pair, then read off groups with find.
Equivalence in compilers
Type inference by unification treats type variables as elements and unifying two as a union; the representative of the group is the type that variable currently stands for.

SOLVE IT YOURSELF

Solve it: count connected groups

This one is yours to write — in Python or TypeScript, running for real in your browser. Build a Union-Find, wire up the edges, and count how many separate groups remain. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement count_components(n, edges): given n items (0…n-1) and a list of [a, b] connections, return the number of connected groups. Use Union-Find — start with n groups and union each edge; every successful merge drops the count by one.

HINTS — 4 IDEAS

Start with n groups: parent[i] = i — everyone leads themselves.
find(x) follows parent pointers up to the root (add path compression for speed).
union(a, b): find both roots. If they differ, point one at the other and decrement the count.
If the two roots are already equal, the edge is redundant (a cycle) — the count does not change.

CPython · WebAssembly

QUICK CHECK

Did it stick?

See every answer, with the reasoning

You call union(a, b) and find(a) already equals find(b). What does that tell you?
Answer: a and b are already connected — this edge would close a cycle — Equal leaders means they are already in the same set. Adding the edge would create a cycle, so Kruskal skips it and union returns false.
What does path compression actually change?
Answer: It re-points every node on a find path directly at the root — After walking to the root, path compression sets each visited node’s parent to the root, flattening the tree so future finds are near-instant.
With union by rank and path compression, the amortized time per operation is…
Answer: O(α(n)) — effectively constant — The inverse Ackermann function α(n) is smaller than 5 for any n you could ever store, so each operation is effectively constant time.

FAQ

Union-Find, answered

What is Union-Find?

A data structure — the Disjoint Set Union — that tracks items split into groups. It answers find(x) (who leads x's group?) and union(a, b) (merge two groups). Two items are connected exactly when they share a leader.

What do union by rank and path compression do?

Union by rank attaches the shorter tree under the taller one; path compression re-points every node touched during a find straight at the root. Together they give near-constant amortized time.

What's the time complexity?

O(m · α(n)) for m operations, where α is the inverse Ackermann function — under 5 for any real n, so effectively constant per operation. Space is O(n).

How does it detect a cycle?

Before each union(a, b), check find(a) == find(b). If they're already equal, the edge would close a cycle. That's the exact test Kruskal's algorithm uses to skip edges.

Can you un-merge two groups?

Not cheaply. Plain Union-Find only ever merges. Removing a connection needs a different approach (offline processing, link-cut trees, or rebuilding), which is why it shines on incremental connectivity.

Finished this one? 0 / 99 Algorithms done

NextThe Cheapest Grid: Kruskal's MST Next on the “What is connected to what” ladder · rung 2 of 5

This idea in other formats

Coding challengeUnion-Find (Connected Components)

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Algorithms →

Pushing Water Through Pipes: Dinic’s Max-Flow