Disjoint Set

Hard

Union by rank plus path compression

Problem

Implement a Disjoint Set Union (union-find) with path compression and union by rank/size.

In simple words

Group items into sets; find each item's leader and merge two groups fast.

The idea

Each set is a tree identified by its root. Path compression flattens the tree during find, and union by rank or size attaches the smaller tree under the larger — together they make both operations effectively constant time.

The trick

Amortised near O(1) — the inverse Ackermann function.
Both optimisations matter; either alone leaves a worse bound.
Ideal when edges arrive incrementally and you only need connectivity.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:: union(1,2); find(2)
Output:: root of 1

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.