Union-Find (disjoint set)
mediumEither optimisation alone gives O(log n); together they give the inverse Ackermann function, which stays below 5 for any input you will ever have. Watch a long chain flatten on its first query.
O(α(n)) ≈ O(1)Worst O(log n) without both optimisationsSpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How union-find (disjoint set) works
Union-Find maintains a collection of disjoint sets under two operations: find(x) returns the representative of x's set, and union(a, b) merges two sets. Each set is a tree of parent pointers; the root is the representative. Two elements are connected exactly when their finds return the same root.
Left alone, the trees degrade into chains and find costs O(n). Two fixes, each one line. Union by rank hangs the shorter tree under the taller, so height only grows when equal-rank roots merge. Path compression re-points every node walked during a find directly at the root, flattening the tree behind you.
Either fix alone yields O(log n) per operation; together they yield amortised O(α(n)) - inverse Ackermann - which stays below 5 for any input that fits in this universe. Effectively constant. The visualizer feeds the default graph's edges through union in order; the edges it skips are precisely the ones that would close a cycle.
Step by step
- All 8 vertices begin as their own root with rank 0 - eight singleton sets, every parent pointer aimed at itself.
- Union A-B: both finds return immediately. Equal ranks, so B hangs under A and A's rank rises to 1.
- Union A-D: rank 1 versus rank 0, so D hangs under A and the height does not grow - union by rank at work.
- Union B-C: find(B) walks one step up to A; find(C) is already a root. Different roots, so C joins A's set.
- Edge D-E arrives after E has already joined: both finds return A. Same set, so the union is refused - this edge would close a cycle.
- Compression has little to do in this run - union by rank kept every tree two levels deep, so each find walks at most one step.
- After all 10 edges: 7 merges accepted, 3 refused as cycles, and one set of 8 remains - the graph is connected.
Complexity
| Average time | O(α(n)) ≈ O(1) |
|---|---|
| Worst case time | O(log n) without both optimisations |
| Space | O(n) |
Reference implementation
Python
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already in the same set
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra # attach the shorter tree
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return TrueJavaScript
class DSU {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false;
if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra;
if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
return true;
}
}Worth noticing
Two optimisations, and you need both
Union by rank keeps trees shallow by always hanging the shorter one underneath. Path compression flattens whatever depth remains, every time you look something up. Either alone gives O(log n); together they give the inverse Ackermann function - effectively constant.
Path compression is why find is not a plain lookup
Every find re-points the nodes it walked directly at the root. The work is paid once and the same query afterwards costs a single step - watch a long chain collapse the first time it is queried.
It answers connectivity, not paths
DSU tells you whether two things are in the same group and nothing else - no route, no distance. That narrowness is what makes it so cheap, and it is exactly enough for Kruskal's algorithm and cycle detection.
α(n) is at most 4 for any n you will ever have
The inverse Ackermann function grows so slowly that it stays below 5 for inputs larger than the number of atoms in the universe. Treating amortised DSU operations as O(1) is fair in practice.
Common pitfalls
- Writing find without compression and union without rank. The trees decay into chains and each operation drifts towards O(n) - the structure's whole advantage evaporates.
- Unioning the elements instead of their roots. parent[b] = a corrupts the forest; it must be the roots that merge, with the rank comparison deciding which one wins.
- Treating rank as exact height. After compression it is only an upper bound - that is why it is called rank, and comparing real heights instead is wasted work.
- Ignoring union's return value. Returning false on same-root pairs is the cycle detector; Kruskal and Redundant Connection are built on exactly that bit.
- Expecting paths or distances out of it. Union-Find answers connectivity only - it has no idea how two elements are connected, which is precisely why it is fast.
Where it is used
- The cycle check inside Kruskal's minimum spanning tree algorithm - its most famous employer.
- Dynamic connectivity: friend circles, network reachability, percolation - queries interleaved with new connections.
- Connected-component labelling in image processing, merging adjacent pixels of the same region.
- Interview classics: Number of Provinces, Accounts Merge, Redundant Connection, Number of Islands II.
Frequently asked questions
What is the time complexity of Union-Find?
With both path compression and union by rank, amortised O(α(n)) per operation - inverse Ackermann, below 5 for any physically possible n, so effectively O(1). Without both optimisations it is O(log n) per operation. Space is O(n) for the parent and rank arrays.
What is the inverse Ackermann function?
The inverse of the fastest-growing function in common use, so itself the slowest-growing: α(n) is at most 4 for any n up to a tower of exponentials vastly exceeding the atoms in the universe. It is the proven amortised bound for the two optimisations combined.
Do I need both path compression and union by rank?
For the α(n) bound, yes - either alone gives O(log n). In practice path compression alone performs excellently, and rank costs only two more lines. In interviews, write find with compression from memory and mention rank; the trade-off is a common follow-up question.
Can Union-Find tell me the path between two nodes?
No. It compresses away exactly that information - parent pointers stop reflecting original edges the moment a find flattens them. It answers same set or different set, nothing more. If you need the actual route, run BFS or DFS on the graph itself.