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

  1. Everyone is their own leader. Start with n singletons: parent[i] = i.
  2. find(x): walk up to the root. Follow parent pointers until a node points to itself — that node is the group's leader.
  3. union(a, b): join two roots. Find both leaders. If they differ, point one at the other — two groups become one.
  4. 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
  1. Start with n groups: parent[i] = i — everyone leads themselves.
  2. find(x) follows parent pointers up to the root (add path compression for speed).
  3. union(a, b): find both roots. If they differ, point one at the other and decrement the count.
  4. 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.

RESULT

—

Next → sort the edges by weight and union them cheapest-first, skipping any that close a cycle. That's Kruskal's Minimum Spanning Tree.

▶  Watch it explained

Prefer a video walkthrough?

Finished this one? 0 / 99 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

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →
Challenges →