Track which items belong to the same group, and merge groups instantly. Two small optimisations take it from linear to effectively constant time — and Kruskal's MST algorithm depends on it entirely.
Controls
Forest of Sets
step 0
parent[] array
Insight
Each set is a tree; the root is the set's representative. Find walks to the root, Union links one root under another.
groups8
max depth1
last find steps–
Complexity
With both optsO(α(n))
No optimisationsO(n)
SpaceO(n)
Union-Find (Disjoint Set)
Two optimisations that turn linear into effectively constant.
Start here
Union-Find maintains a collection of non-overlapping sets and supports two operations: find(x) — which set does x belong to? — and union(a, b) — merge the two sets containing a and b.
The Structure
Each set is stored as a tree, with every element pointing to a parent. The root represents the whole set. Two elements are in the same set exactly when they have the same root.
Union is therefore trivial: point one root at the other. All the difficulty is in keeping find fast, because it must walk to the root.
Optimisation 1: Union by Rank
Naively linking roots can build a long chain — press Build a bad chain with both optimisations off to see one. Depth grows to n and every find becomes O(n).
Union by rank always attaches the shorter tree under the taller one. The result never gets deeper than necessary, keeping depth at O(log n). Toggle the checkbox and rebuild the chain to compare.
Optimisation 2: Path Compression
When find(x) walks to the root, it already knows the answer for every node along the way — so it re-points them all directly at the root on the way back.
Press Find on a deep node with compression on and watch the tree flatten in a single operation. Each find makes all subsequent finds cheaper, so the cost is amortised away.
The Famous Complexity
With both optimisations, m operations on n elements cost O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that for any n that fits in the observable universe, α(n) < 5.
It is not technically constant, but it is constant for every practical purpose — one of the most striking results in data-structure analysis.
Where It Is Used
Kruskal's MST — sort edges, add one if its endpoints are in different sets. Union-Find is what makes the cycle check fast.
Connected components — in a graph, an image (flood fill), or a network.
Percolation and clustering — does a path exist from top to bottom?
Account or record merging — treating "these two IDs are the same person" as a union.
Tracking which things are connected
Union-Find (a disjoint-set union structure) answers one question extremely fast: are these two elements in the same group? And it supports merging groups.
Two operations:
find(x) — return a representative of x's set. union(x, y) — merge the sets containing x and y.
Two elements are connected exactly when find(x) == find(y).
Each set is stored as a tree, with every element pointing at its parent and the root representing the set. The root points to itself.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # each element its own root
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already connected
if self.rank[rx] < self.rank[ry]: # union by rank
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
Why the two optimisations matter
Without them, the trees can degenerate into chains and find becomes O(n). Two techniques together make it effectively constant.
Union by rank (or by size) always attaches the shorter tree under the taller one, so depth grows logarithmically at worst rather than linearly.
Path compression flattens the tree during find: every node on the path is re-pointed closer to the root, so subsequent finds are shorter. The line self.parent[x] = self.parent[self.parent[x]] is path halving — simpler than full compression and just as effective in practice.
Together they give an amortised complexity of O(α(n)), where α is the inverse Ackermann function. For any n that fits in the universe, α(n) < 5 — so it is constant for all practical purposes.
Optimisations
Complexity per operation
Neither
O(n)
Union by rank only
O(log n)
Path compression only
O(log n) amortised
Both
O(α(n)) — effectively O(1)
That is one of the most striking results in data structures: two short additions to an obvious algorithm take it from linear to essentially constant.
Kruskal's algorithm, the canonical use
Union-Find exists largely because of this. Kruskal's minimum spanning tree algorithm sorts all edges by weight and adds each one unless it would form a cycle — and "would form a cycle" means "both endpoints are already connected".
def kruskal(n, edges):
uf = UnionFind(n)
mst, total = [], 0
for weight, u, v in sorted(edges):
if uf.union(u, v): # False if already connected
mst.append((u, v, weight))
total += weight
return mst, total
The union returning False is the cycle check. There is no separate cycle detection, because Union-Find already knows.
O(E log E) for the sort, plus effectively O(E) for the unions — so sorting dominates, and the connectivity bookkeeping is free.
What the two optimisations are actually worth
Union-Find is a handful of lines, and then two optimisations turn its near-linear complexity from a claim into a fact. Both are one line each, so the honest way to judge them is to count pointer hops with each combination switched on and off.
example_01.pyPython
class DSU:
def __init__(self, n, by_rank=True, compress=True):
self.parent = list(range(n))
self.rank = [0] * n
self.by_rank, self.compress = by_rank, compress
self.hops = 0
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
self.hops += 1
if self.compress:
while self.parent[x] != root: # second pass: re-point
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.by_rank:
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
else:
self.parent[ra] = rb # arbitrary: builds a chain
return True
n = 2000
print("%d elements, unioned in the worst order, then every element queried"
% n)
print("%-26s %14s %14s" % ("variant", "pointer hops", "tree depth"))
for by_rank in (False, True):
for compress in (False, True):
d = DSU(n, by_rank, compress)
for i in range(n - 1):
d.union(i, i + 1) # a chain, if nothing prevents it
d.hops = 0
for i in range(n):
d.find(i)
depth = 0
for i in range(n):
k, c = i, 0
while d.parent[k] != k:
k = d.parent[k]; c += 1
depth = max(depth, c)
name = "%s + %s" % ("rank" if by_rank else "no rank",
"compress" if compress else "no compress")
print("%-26s %14d %14d" % (name, d.hops, depth))
# The first row is the degenerate case: unioning 0-1, 1-2, 2-3 in order
# with no rank builds one long chain, and every find walks it. That is
# O(n) per query -- a linked list wearing a tree's name.
#
# Either optimisation alone fixes it, and they fix it differently. Union
# by rank PREVENTS the deep tree from forming; path compression allows it
# to form and then flattens it on the way back out. Together the depth
# collapses to 1 and a find is a single lookup.
#
# The famous complexity is O(alpha(n)) amortised, where alpha is the
# inverse Ackermann function. It is not a constant, but:
best = DSU(n, True, True)
for i in range(n - 1):
best.union(i, i + 1)
best.hops = 0
for i in range(n):
best.find(i)
print()
print("alpha(n) stays below 5 for any n that fits in the observable universe.")
print("with both optimisations, %d finds cost %d hops -- %.2f each."
% (n, best.hops, best.hops / n))
# Now what it is FOR. Union-Find answers "are these two in the same
# group" under merges, which is exactly Kruskal's cycle test:
edges = [(1, "a", "b"), (2, "b", "c"), (2, "a", "c"), (3, "c", "d")]
names = {}
d = DSU(4)
for w, u, v in edges:
for x in (u, v):
names.setdefault(x, len(names))
print()
d = DSU(len(names))
total = 0
for w, u, v in sorted(edges):
if d.union(names[u], names[v]):
total += w
print(" take %s-%s (weight %d)" % (u, v, w))
else:
print(" skip %s-%s (weight %d) -- would close a cycle" % (u, v, w))
print(" spanning tree weight:", total)
# The b-c edge was rejected without any search of the tree built so far:
# b and c were already connected through a, and one find on each end
# said so.
# That is the whole contribution: a cycle test that costs almost nothing,
# which is what makes Kruskal's algorithm practical.
Output
Guided tour
Union a few pairs and watch separate trees form. The group counter drops by one per successful merge.
Union two elements already in the same set. Nothing changes — and that check is exactly how Kruskal avoids creating a cycle.
Turn off both optimisations and press Build a bad chain. Depth grows linearly and finds get slow.
Turn path compression back on and run Find on the deepest node. The tree flattens in one step.
Compare max depth with rank on and off. Union by rank prevents the tall trees; compression fixes the ones already made.
Worth remembering
Union-Find answers "same group?" and "merge groups" in effectively constant time, using union by rank to keep trees shallow and path compression to flatten them on the way. It is the structure that makes Kruskal's algorithm and fast connected-component queries possible.
Where else it is used
Connected components in a static or growing graph — union every edge, then count distinct roots.
Cycle detection in an undirected graph. A union that returns False means the edge closes a cycle.
Percolation and network reliability — adding links and asking when the network becomes connected.
Image segmentation — merging adjacent similar pixels into regions.
Least common ancestor offline (Tarjan's algorithm).
Equivalence classes — type unification in compilers, merging duplicate records in entity resolution.
Grid problems — counting islands, or determining when a path exists across a grid as cells are opened.
The grid case is a good example of the structure's fit: cells are unioned as they are opened, and asking whether the top and bottom are connected is one find comparison. Re-running BFS after each change would be far more expensive.
What it cannot do
The critical limitation: Union-Find supports merging, not splitting. There is no efficient disconnect(x, y).
That is because path compression destroys the tree's original shape — the structure knows which elements are together and not how they came to be, so it cannot undo a union.
Consequences:
Dynamic connectivity with deletions needs a different structure (link-cut trees, or offline processing).
Time-travel queries — "were these connected at step k?" — need a persistent or rollback variant. A rollback version exists, and it must forgo path compression, giving O(log n) instead.
Directed connectivity is not what it does. Union-Find handles undirected, symmetric relationships; strongly connected components need Tarjan's or Kosaraju's algorithm.
Need
Structure
Merge groups, test membership
Union-Find
Deletions as well
Link-cut trees, or offline
Directed reachability
DFS, transitive closure
Shortest paths
BFS or Dijkstra
Component sizes
Union-Find with a size array
Practical variations
Tracking component sizes. Keep a size array updated on union. Useful for "largest component" queries and for union by size, which performs comparably to union by rank.
Counting components. Start at n and decrement on each successful union. One integer, and it answers "is the graph connected yet?" in O(1).
Weighted Union-Find. Store an offset alongside each parent pointer to maintain relative values — used for problems involving equations between variables, or relative positions.
Union-Find on arbitrary keys. Replace the arrays with dictionaries so elements need not be integers 0..n−1.
Questions people ask
What does O(α(n)) mean? The inverse Ackermann function, below 5 for any conceivable n. Treat it as constant.
Can I undo a union? Not with path compression. A rollback variant exists without it, at O(log n).
Union by rank or by size? Both work and give the same complexity. Size is slightly more intuitive and lets you query component sizes for free.
Does it work for directed graphs? No — it models symmetric connectivity only.
Why does path compression not break correctness? Because only the root identifies the set, and re-pointing nodes closer to the same root changes nothing about membership.
How does it compare with BFS for connectivity? BFS answers one query in O(V+E). Union-Find answers many queries on a growing graph in near-constant time each.
Recap in one screen
find returns a set's representative; union merges two sets; equality of representatives means connected.
Union by rank keeps trees shallow; path compression flattens them during find.
Together they give amortised O(α(n)) — effectively constant for any real input.
Kruskal's MST algorithm is the canonical use, where union returning False is the cycle check.
It supports merging only — no efficient deletion, and no directed reachability.
Run it in Python
The same twelve operations run twice: once on a naive implementation, once with union by rank and path compression, with pointer hops counted. The difference between the two counts is the whole reason the optimisations exist.
union_find.pyPython 3
# Union-Find (disjoint set union): which things are in the same group?
class NaiveDSU:
def __init__(self, items):
self.parent = {x: x for x in items}
self.hops = 0
def find(self, x):
while self.parent[x] != x: # walk up to the root
self.hops += 1
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra != rb:
self.parent[ra] = rb # attach blindly - this is the problem
return True
return False
class DSU(NaiveDSU):
def __init__(self, items):
super().__init__(items)
self.rank = {x: 0 for x in items}
def find(self, x):
root = x
while self.parent[root] != root:
self.hops += 1
root = self.parent[root]
while self.parent[x] != root: # path compression: flatten on the way back
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]: # union by rank: shorter under taller
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
items = list(range(10))
merges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
for cls in (NaiveDSU, DSU):
dsu = cls(items)
for a, b in merges:
dsu.union(a, b)
for x in items: # now ask about every element
dsu.find(x)
print(f"{cls.__name__:>9}: {dsu.hops} pointer hops")
print()
dsu = DSU(items)
for a, b in [(0, 1), (2, 3), (1, 3), (5, 6)]:
print(f"union({a}, {b}) merged:", dsu.union(a, b))
groups = {}
for x in items:
groups.setdefault(dsu.find(x), []).append(x)
print("groups:", list(groups.values()))
print("connected(0, 3):", dsu.find(0) == dsu.find(3))
print("connected(0, 5):", dsu.find(0) == dsu.find(5))
Output
How the code works
self.parent = {x: x for x in items}Every element starts as its own root, so there are n groups of one. “Which group is x in?” is always answered by walking to the root, and the root's identity is the group's name.
self.parent[ra] = rb # naiveAttaching without looking at the shapes is what builds a chain. Merge in a line, as the sample does, and find degrades to O(n) — a linked list wearing a tree's name.
if self.rank[ra] < self.rank[rb]: ra, rb = rb, raUnion by rank: hang the shorter tree under the taller one so the depth does not grow. Rank is an upper bound on height, not the exact height, which is why compression can leave it stale without breaking anything.
while self.parent[x] != root: self.parent[x], x = root, self.parent[x]Path compression. Every node touched on the way up is re-pointed straight at the root, so the next query on any of them is one hop. The work of the walk is what pays for the next walk.
dsu.hopsTogether these give near-constant amortised time — O(α(n)), where α is the inverse Ackermann function and is below 5 for any n that fits in a computer. The hop counts printed here are that theory, measured.
Change one thing
Raise items to range(1000) with the same chain of merges. The naive count explodes quadratically; the optimised one barely moves.
Delete only the compression loop, keeping rank. Most of the win survives — either optimisation alone is already good.
Add a count field decremented on each successful union. That is how union-find answers “how many connected components?” in O(1).
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
What does path compression do?
The walk pays for the next walk. Every node on the path becomes one hop from the root, so repeat queries are effectively free.
Union by rank exists to prevent:
Attaching blindly, as the naive version does, builds a linked list wearing a tree's name - and find degrades to O(n), which the program's hop counts show directly.
With both optimisations, the amortised cost per operation is:
The inverse Ackermann function grows so slowly that it is a constant for practical purposes - but it is not literally O(1).
Cheat sheet
Union-Find (Disjoint Set)
Track which items belong to the same group, and merge groups instantly. Two small optimisations take it from linear to effectively constant time — and Kruskal's MST algorithm depends on it entirely.
Efficiency of a Good But Not Linear Set Union AlgorithmTarjan, Journal of the ACM 1975
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.