Union-Find (Disjoint Set)

Track which nodes belong to the same group and merge groups quickly, used to detect cycles and build networks.

What is union-find?

Union-find tracks a collection of items split into disjoint groups, and answers one question fast: are these two items in the same group? Two operations do all the work — union(a, b) merges a's group and b's group, and find(a) walks up to the group's root so you can compare roots instead of members.

Done naively, that walk can degrade to a straight line and cost O(n) per call. With union by size and path compression, it settles to nearly O(1) amortized.

Find
Ask which group's root a given item ultimately belongs to
Union
Merge two items' groups into one by pointing one root at the other
Root
The representative item at the top of a group — every member eventually points to it

Why union-find at all?

Picture a company where you only care about one thing: which team is this person ultimately part of. When two teams merge, you don't rebuild the org chart — you just point one team's lead at the other's.

Ask "same team?" and you walk each person up to their team's lead and compare. No scanning every member, no rebuilding anything — just a pointer flip per merge.

Six people, merging by team lead
Teams6Last merge—

Each merge points one lead at another. Teams only ever shrink.

What kinds of problems does it solve?

Four common shapes. Every one of them boils down to the same move: before you connect two items, ask find whether they're already in the same group.

Detect a cycle

Before adding an edge, call find on both ends. If they already share a root, this edge doesn't connect anything new — it closes a loop. That's the extra, redundant connection.

Adding edges one at a time · watch for a repeat root
Edge0–1Verdictno cycle

Same root on both ends before you union → this edge is the redundant one.

Count connected groups

Union every pair that's directly connected, then count the distinct roots left standing. That count is the number of separate groups — provinces, clusters, components, whatever the problem calls them.

Five cities · union on every direct road
Roads unioned0Components5

Every union can only merge two roots into one — components never goes up.

Merge groups that share something

Two accounts that share even one email address are the same person. Union them whenever you spot a shared email, and every account in the final group belongs to one merged identity.

Four accounts · union on a shared email
Shared email found—Groups4

Shared emails chain accounts together, even across pairs that never matched directly.

Check the whole thing connects

A valid tree needs exactly n - 1 edges and no cycle. Union every edge — if find ever says two ends already share a root, it's not a tree. If you finish with one group and the right edge count, it is.

Four nodes, three edges · no repeats allowed
Edges used0Groups4

n − 1 edges, one group left, never a repeated root — that's a valid tree.

Two optimizations

Naive union-find works, but a bad merge order can turn it into a straight line — every find degrading to O(n). These two changes, usually applied together, are what keep it fast.

Union by size

When merging two groups, always attach the smaller tree under the bigger one's root — never the other way round. That one rule keeps trees shallow instead of letting them grow into a chain.

Group of 4 vs. a lone node · smaller attaches under bigger
Sizes4 vs 1AttachE under A

The 1-node tree bends to the 4-node tree. Never the reverse.

union-by-size.tsTypeScript
function union(parent: number[], size: number[], a: number, b: number): void {
  const rootA = find(parent, a);
  const rootB = find(parent, b);
  if (rootA === rootB) return; // already connected

  if (size[rootA] < size[rootB]) {
    parent[rootA] = rootB; // attach the smaller tree under the bigger
    size[rootB] += size[rootA];
  } else {
    parent[rootB] = rootA;
    size[rootA] += size[rootB];
  }
}

Path compression

While find walks up a chain to the root, point every node it passes through directly at that root. The first walk pays for itself once — every find after it is nearly instant.

A 4-node chain · flattened after one find
find(0)3 hopsNext find(0)1 hop

Every node on the path now points straight at the root.

path-compression.tsTypeScript
function find(parent: number[], x: number): number {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]); // point straight at the root
  }
  return parent[x];
}

Where it works — and where it breaks

Both optimizations are cheap to add and nearly free to skip by accident. Forget them, and the wrong merge order quietly turns every find into a linear scan.

Balanced — union by size + path compression

Every merge attaches the smaller tree under the bigger one, and every find flattens what it touches. The tree stays shallow no matter what order the unions arrive in.

Five nodes · height stays at 2
0 → 4
1 → 4
2 → 4
3 → 4
4 (root)
Height2find cost≈ O(1)

Unbalanced — no rank, no compression

Always attach the newest node's root under whatever came before it, and the "tree" is just a linked list wearing a disguise. find on the last node walks every node that came before it.

Five nodes · height grows to 4
0 → 1
1 → 2
2 → 3
3 → 4
4 (root)
Height4find costO(n)

Related concepts