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.

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.

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?

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 / 9 Algorithms done

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 from Vibe Engines

Gradient Descent: The Descent

Paper Breakdowns →

Attention Is All You Need