What is Union-Find?
Data Structures·3 min read·code in python
Union-Find, also called disjoint set union (DSU), keeps track of which items belong to the same group while groups keep merging. It answers two questions: find, which group is this item in, and union, put these two groups together. With path compression and union by size, both cost almost constant time.
The intuition: every group has one representative
Picture a hall of people forming teams. Each team picks one person to speak for it. To ask whether two people are on the same team, you do not compare the teams: you ask each person who speaks for them, and compare those two names.
That speaker is the representative, or root. Each item stores a parent, and following parents leads to the root. Merging two teams is one pointer: make one root point at the other.
Find, union, and the two tricks that make them fast
A plain version can degrade into a long chain, so every find walks a list. Two small changes fix it.
Union by size or rank: when merging, hang the smaller tree under the bigger one, so the tree stays shallow. Path compression: while finding a root, point every node you passed straight at it, so the next lookup is one step. Together they bring the amortised cost to the inverse Ackermann function, under five for any input you will ever run.
When it beats a traversal
BFS or DFS answers "which nodes are connected?" for a graph you already have. Union-Find answers it while the edges are still arriving, and after each edge the answer is ready.
That is why it is the engine of Kruskal's minimum spanning tree (add the cheapest edge unless it closes a cycle), of cycle detection in an undirected graph, and of any problem that merges accounts, islands or intervals as it reads them.
The code
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # every item starts in its own group
self.size = [1] * 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, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already together: this edge closes a cycle
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # hang the smaller tree under the bigger
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def connected(self, a, b):
return self.find(a) == self.find(b)Run it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | O(a(n)) amortised per operation, where a is the inverse Ackermann function. |
|---|---|
| Space | O(n) for parent and size. |
Without path compression and union by size the worst case slides back to O(n) per find, so the two tricks are the algorithm, not an optimisation.
When to use it
- Connected components while edges keep arriving, instead of re-running a traversal.
- Kruskal's minimum spanning tree: take an edge only when it joins two different groups.
- Cycle detection in an undirected graph: an edge inside one group closes a cycle.
- Merging things that are the same: duplicate accounts, islands on a grid, equal variables.
Watch out for
- Splitting groups: union-find merges, it cannot undo a union without extra work.
- Directed graphs: it has no sense of direction, so use a traversal or SCC instead.
- Path questions: it tells you whether two items are connected, not the route between them.
- One-shot components on a fixed graph: a single BFS or DFS is simpler.
Union-Find: questions we get
What is the time complexity of union-find?
With path compression and union by size, each find or union is O(a(n)) amortised, where a is the inverse Ackermann function. For any practical n that is under five steps, so people call it constant.
Union by rank or union by size?
Both keep the tree shallow and both are fine. Size hangs the smaller tree under the larger one; rank uses an upper bound on height. Size is easier to reason about because you can read the group size straight off the root.
Why does path compression matter?
It flattens the tree while answering a query: every node on the path is pointed straight at the root, so later lookups take one step instead of walking the chain again.
Union-Find or DFS for connected components?
DFS is fine when the graph is complete before you start. Union-Find wins when edges arrive over time, or when you need the answer after every edge, as in Kruskal.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor