Union-Find (Disjoint Sets)
Track which items belong to the same group with near-constant-time merge and lookup, using path compression and union by size.
intermediate35 min#union-find#disjoint-set#graphs#connectivity
Prerequisites: Arrays and Dynamic Arrays, Graphs: Representations, BFS and DFS
Why it matters
Many problems boil down to one question asked repeatedly: are these two things in the same group, and can I merge their groups? Friends-of-friends networks, connected regions in an image, grouping accounts that share an email, detecting a cycle while adding edges, and Kruskal's minimum spanning tree all need it. A graph search answers connectivity once in O(n). Union-find answers it after each new edge in nearly constant time, which is what you need when edges arrive over time.
Intuition
Picture a room full of people, each initially standing alone. Every group has a leader. To check whether two people are in the same group, ask each for their leader; if the leaders match, they are together. To merge two groups, make one leader report to the other.
Store this as a forest: each item points to a parent, and a root is its own parent. "Find" climbs to the root. "Union" links one root under another.
How it works
Start with parent[i] = i for every item. Two operations:
- find(x): follow parent pointers until you reach a root (
parent[r] == r). - union(a, b): find both roots; if different, link one under the other.
Here is the demo from the code below as a forest. Each arrow points from an item to its parent, and green items are roots.
Each tree in the forest is one set; the root is its leader. Merging two sets only moves one arrow, and a redundant union changes nothing.
Used naively, a chain of unions can build a long skinny tree where find costs O(n). Two small tricks fix that.
Union by size (or rank): always attach the smaller tree under the larger one. A tree's depth then only increases when it at least doubles in size, so depth is at most log n.
Path compression: while climbing in find, make nodes point closer to the root. The code below uses path halving: each visited node jumps to its grandparent. Later finds on those nodes are shorter.
before: 4 -> 3 -> 2 -> 1 -> 0 (root) find(4) walks 4 steps
after find(4) with path halving:
4 -> 2 -> 0, 3 -> 2, 1 -> 0 later finds are shorter
Here is path halving running on that chain, with the parent array underneath.
Cell i holds parent[i]. Every visited node jumps to its grandparent, so the next find on any of these nodes is shorter.
With both tricks, the amortized cost per operation is O(alpha(n)), where alpha is the inverse Ackermann function. It grows so slowly that it is at most 4 for any input that fits in the universe. In practice, treat it as constant.
Tracking the count of components is easy: start with n and subtract one every time a union actually merges two different roots. A union that finds the roots already equal is a redundant edge, which is exactly how you detect a cycle in an undirected graph.
| Operation | Time | Notes |
|---|---|---|
| make-set (initialize n items) | O(n) | parent[i] = i |
| find | O(alpha(n)) | Amortized, with compression and size |
| union | O(alpha(n)) | Two finds plus a link |
| Space | O(n) | Parent and size arrays |
| Without optimizations | O(n) per op | Degenerate chain |
Code: a reusable UnionFind
The demo adds five edges to a graph of 7 nodes. Edge (2, 0) closes a cycle with the first two edges, and (5, 5) is a self-loop, so both are redundant.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # every node starts as its own root
self.size = [1] * n
self.components = n
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
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller tree under larger
self.size[ra] += self.size[rb]
self.components -= 1
return True
edges = [(0, 1), (1, 2), (3, 4), (2, 0), (5, 5)]
uf = UnionFind(7)
redundant = [e for e in edges if not uf.union(*e)]
print(uf.components)
print(len(redundant), *redundant[0])
print(str(uf.find(0) == uf.find(2)).lower(), str(uf.find(0) == uf.find(3)).lower())class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i); // every node is its own root
this.size = new Array(n).fill(1);
this.components = n;
}
find(x) {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]]; // path halving
x = this.parent[x];
}
return x;
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false; // already connected
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra; // attach smaller tree under larger
this.size[ra] += this.size[rb];
this.components--;
return true;
}
}
const edges = [[0, 1], [1, 2], [3, 4], [2, 0], [5, 5]];
const uf = new UnionFind(7);
const redundant = edges.filter(([a, b]) => !uf.union(a, b));
console.log(uf.components);
console.log(redundant.length, ...redundant[0]);
console.log(uf.find(0) === uf.find(2), uf.find(0) === uf.find(3));Both versions print three lines: 4 (components: one of 0,1,2; one of 3,4; and singletons 5 and 6), 2 2 0 (two redundant edges, the first being 2 0), and true false (0 and 2 are connected, 0 and 3 are not).
Common pitfalls
- Unioning the items instead of the roots: always call
findfirst and link the roots. Linking arbitrary nodes can break the tree. - Forgetting path compression: the code stays correct but loses its speed guarantee.
- Recursive find on huge inputs: a recursive find can overflow the stack on a deep tree in Python. The iterative loop used here avoids that.
- Mapping non-integer items: union-find indexes arrays. Map strings or emails to integer ids first using a dictionary or
Map. - Reading
parent[x]as the root: after unions,parent[x]may not be the root. Always callfind(x).
Practice
Number of provinces easy
Hint
Each connected pair of cities is a union. Count components at the end.
Show solution
Create a UnionFind(n). For every pair i, j marked connected in the matrix, call union(i, j). The answer is components. O(n^2 * alpha(n)) because the matrix has n^2 entries.
Redundant connection medium
Hint
Process edges in order. Which edge joins two nodes that are already connected?
Show solution
Union each edge as it comes. The first edge for which union returns false closes a cycle, so return it. The graph started as a tree plus one extra edge, so that edge is the answer. O(n * alpha(n)).
Accounts merge medium
Hint
Treat each email as a node. Accounts sharing any email belong together.
Show solution
Map each distinct email to an integer id. For each account, union the id of its first email with every other email in that account. Then group emails by find(id), attach the owner name, and sort each group. Total near O(E * alpha) plus the sort.
Minimum spanning tree (Kruskal) hard
Hint
Sort edges by weight. Add an edge only if it connects two different components.
Show solution
Sort edges by weight ascending. For each edge, if union(u, v) returns true, add its weight to the total; otherwise skip it (it would form a cycle). Stop after n - 1 accepted edges. The sort dominates: O(E log E). This is correct by the greedy cut property.
Interview questions
- What two optimizations make union-find fast, and why? Union by size keeps trees shallow; path compression flattens them during finds. Together they give near-constant amortized time.
- How do you detect a cycle in an undirected graph with union-find? Union the endpoints of each edge; if they already share a root, that edge closes a cycle.
- When would you prefer BFS or DFS to union-find? For a one-off connectivity or path query on a fixed graph. Union-find shines when connections are added incrementally and you query often, and it cannot give you the actual path.
- Can it handle deleting an edge? Not directly; it is a merge-only structure.
Interviewers look for: iterative find with compression, union by size or rank, a component counter, and using the boolean result of union to spot redundant edges.
Quick check
While adding edges one by one, union(a, b) finds that a and b already have the same root. What does this mean?
Finished this lesson?
Further resources
- Disjoint-set data structure (Wikipedia) (article)
- Kruskal's algorithm (Wikipedia) (article)