Union-Find (also called a disjoint set union, or DSU) shows up in interviews more often than people expect: counting connected components, detecting a cycle in an undirected graph, redundant connection, number of provinces, and grouping equivalent strings. Once you can write it from memory in two minutes, a whole family of graph questions becomes easy.
The idea
Every element starts in its own set. Each set is a tree, and the root of the tree is the set's representative. Two operations matter:
find(x)walks up to the root of x's tree.union(a, b)finds both roots and, if they differ, attaches one root under the other.
The interview-ready version
class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n self.count = n # number of components def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # path halving 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 connected: this edge closes a cycle if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] self.count -= 1 return True
With path compression (here, path halving) and union by size, each operation runs in near-constant amortized time, formally O(α(n)), the inverse Ackermann function. Say that out loud; interviewers like hearing that you know why it is fast.
Three questions it solves directly
- Number of connected components: union every edge, then return
count. - Redundant connection: process edges in order; the first edge where
unionreturnsFalseis the answer. - Accounts merge / equivalent groups: map each item to an index, union items that appear together, then bucket by
find.
When to prefer BFS/DFS instead
If the graph is given once and you only need components, DFS is just as good. Union-Find wins when edges arrive one at a time (dynamic connectivity) or when you need to answer "are these two connected?" many times.
Common mistakes
- Comparing
parent[a] == parent[b]instead offind(a) == find(b). - Forgetting to decrement the component count only on a successful union.
- Using recursion for
findin Python on huge inputs and hitting the recursion limit.
Practice tip
Write the class above five times on paper this week, then solve one connectivity problem a day using it. For live practice where you explain your reasoning out loud, I build Linkjob AI copilot, an assistant for technical interviews (disclosure: I work on it).