Some graph problems don’t care about routes at all. They ask whether two things are connected, how many separate groups there are, or whether adding a link would create a loop. And often the links arrive one at a time, with questions in between. You could rerun a BFS after every new edge, but that’s O(V + E) per question. Union-find, also called a disjoint-set union (DSU), answers those questions in near-constant time per operation.
It does that by remembering much less than a graph does. It knows which group each element belongs to and nothing about how they got there. That’s both why it’s fast and why it’s the wrong tool for anything involving paths.
Every group has a representative
Each element stores a single pointer, parent. Following parent pointers from any element eventually reaches an element that’s its own parent: the root, which represents the whole group. Two elements are in the same group exactly when they have the same root.
Two operations make up the whole interface:
find(x): follow parents fromxto the root and return it.union(a, b): find both roots; if they differ, make one root point to the other, merging the groups.
Initially every element is its own root, so there are n groups of one. Here’s the simplest possible version:
class NaiveUF:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
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 # always hang a's root under b's root
return True
return FalseIt’s correct. It can also be very slow.
How the naive version degrades
The cost of find is the length of the path to the root, and nothing in the naive version stops that path from getting long. Union 0 with 1, then 1 with 2, then 2 with 3, and so on: each root gets hung under the next element, building a chain 0 → 1 → 2 → ... → n-1. A find(0) then walks the entire chain.
The test built exactly that chain, then called find on every element and counted parent hops. It ran the naive class and an optimised one (shown in the next section) on the same sequence of unions:
NaiveUF, n= 1,000: 499,500 parent hops for 1,000 finds
UnionFind, n= 1,000: 999 parent hops for 1,000 finds
NaiveUF, n=10,000: 49,995,000 parent hops for 10,000 finds
UnionFind, n=10,000: 9,999 parent hops for 10,000 findsThe naive version does n(n - 1) / 2 hops, which is quadratic: ten times the elements, a hundred times the work. The optimised one does one hop per non-root element. Union order like this isn’t contrived, either. Processing edges of a long path in order produces it.
Union by size and path compression
Two small changes fix it, and they work best together.
Union by size (or by rank): when merging, attach the root of the smaller group under the root of the larger one. A tree’s height can only increase when it’s merged with a group at least as large, which at least doubles its size, so no tree gets taller than log₂ n.
Path compression: during find, once you know the root, go back along the path and point every node on it directly at the root. The next find on any of them is a single hop.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # every element starts as its own root
self.size = [1] * n
self.components = n
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # path compression: point everything at the root
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 # already connected
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # smaller tree goes under the larger
self.size[ra] += self.size[rb]
self.components -= 1
return TrueTo see path compression on its own, hand-build a chain of six elements and call find(0) once:
before find(0): [1, 2, 3, 4, 5, 5]
after find(0): [5, 5, 5, 5, 5, 5]One walk down the chain flattened it completely. The find here is iterative on purpose: the textbook recursive version (parent[x] = find(parent[x])) is shorter, but on a long chain built before any compression it can hit Python’s recursion limit.
Notice two more things the class does. union returns whether a merge happened, which is the cycle-detection signal below. And it keeps a running components count, decremented on every successful merge, so “how many groups?” is O(1) instead of a scan over all roots.
With both optimisations, a sequence of m operations on n elements runs in O(m · α(n)) time, where α is the inverse Ackermann function. It grows so slowly that it’s at most 4 for any input that could fit in a computer, so in an interview “amortised nearly constant” is the right description. With only one of the two optimisations you get O(log n) per operation, still fine in practice. Space is O(n) for the two arrays.
Groups that keep merging
Here’s the situation union-find is built for: friendships arriving one at a time among seven people, with the number of friend groups tracked as they arrive.
names = ["ana", "ben", "cho", "dev", "eli", "fay", "gus"]
idx = {name: i for i, name in enumerate(names)}
friendships = [("ana", "ben"), ("cho", "dev"), ("ben", "cho"),
("eli", "fay"), ("ana", "dev"), ("fay", "gus")]
uf = UnionFind(len(names))
for a, b in friendships:
merged = uf.union(idx[a], idx[b])
note = "merged two groups" if merged else "already connected: this edge closes a cycle"
print(f"{a}-{b}: {note}; groups now {uf.components}")
print("ana and dev connected?", uf.find(idx["ana"]) == uf.find(idx["dev"]),
" ana and gus?", uf.find(idx["ana"]) == uf.find(idx["gus"]))ana-ben: merged two groups; groups now 6
cho-dev: merged two groups; groups now 5
ben-cho: merged two groups; groups now 4
eli-fay: merged two groups; groups now 3
ana-dev: already connected: this edge closes a cycle; groups now 3
fay-gus: merged two groups; groups now 2
ana and dev connected? True ana and gus? FalseUnion-find maps names to integer indexes first, since it works on array positions. The ana-dev line is the interesting one. Ana and Dev were already connected through ana → ben → cho → dev, so their roots match and union returns False. In an undirected graph, an edge between two already-connected vertices always closes a cycle. That’s the whole of “Redundant Connection” (find the edge to remove to leave a tree), and it’s the check at the heart of Kruskal’s minimum spanning tree algorithm, which sorts edges by weight and keeps each edge only if union succeeds.
What it can’t tell you
Interviewers like to probe the limits, so be explicit about them:
- No paths. The structure knows Ana and Dev are connected, not that the route goes through Ben and Cho. Parent pointers after compression don’t follow original edges at all. If you need the path, use BFS or DFS.
- No direction. Union-find models symmetric relationships. “A depends on B” is a directed edge, and reachability in a directed graph needs a traversal or topological sort.
- No deletions. You can merge groups but not split them. If friendships can end, union-find doesn’t fit (there are offline tricks that process the operations in reverse, but they’re well beyond a typical interview).
A good one-line answer to “when would you use union-find instead of BFS?” is: when edges arrive over time and you only need connectivity or component counts.
Interview practice: Number of Islands with union-find
Given a grid of "1" (land) and "0" (water), count the islands, where an island is land connected horizontally or vertically. The usual answer uses BFS or DFS. Solve it with union-find instead and explain the details.
Answer
Give each cell an index, r * cols + c. Start with every cell as its own component. For each land cell, union it with its land neighbours. You only need to look right and down: the left and up neighbours already did the union with this cell when they were processed, and union is symmetric. At the end, the component count includes every water cell as a lonely singleton, so subtract the number of water cells.
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
water = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "0":
water += 1
continue
for nr, nc in ((r + 1, c), (r, c + 1)): # right and down are enough
if nr < rows and nc < cols and grid[nr][nc] == "1":
uf.union(r * cols + c, nr * cols + nc)
return uf.components - water # every water cell is its own component1 3 5 0
1,000 random grids: union-find count matches BFSThe four grids are the two standard examples (one large island; three islands), a 3 by 3 checkerboard of "1" corners and centre (five islands, since diagonals don’t connect), and a single water cell. The second line is a randomised cross-check against a BFS counter.
Time is O(R · C · α(R · C)), effectively linear in the number of cells, and space is O(R · C) for the parent and size arrays. Compared with BFS, the union-find version is no faster for a single static grid and uses a similar amount of memory. Where it wins is the follow-up: “land is now added one cell at a time; report the island count after each addition” (LeetCode’s Number of Islands II). Rerunning BFS after each addition is O(R · C) per step, while union-find handles each new cell with at most four unions. Mentioning that follow-up shows you know why you’d choose it. You can test your own version on Number of Islands.
Related reading
- Data Structures and Algorithms interview questions
- DSA multiple-choice questions
- Graph DFS States and Cycle Detection, for cycles in directed graphs
- Breadth-First Search and Unweighted Shortest Paths, when you need the route itself
- MIT 6.006 Introduction to Algorithms (Spring 2020)