Union-Find
Union-Find (also called Disjoint Set Union) tracks which elements belong to the same group. It's incredibly efficient for two operations: merging groups together (union) and checking if two elements are in the same group (find).
The Core Idea
Each group has a representative (root). To check if two elements are connected, check if they have the same root. To merge groups, make one root point to the other.
With path compression and union by rank, both operations run in nearly O(1) time - technically O(α(n)), where α is the inverse Ackermann function. For all practical purposes, it's constant.
Classic Implementation
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
# Path compression
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # Already connected
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)Classic: Number of Connected Components
def countComponents(n, edges):
uf = UnionFind(n)
components = n
for a, b in edges:
if uf.union(a, b):
components -= 1 # Merged two groups
return componentsWhen to Use Union-Find
- Connected components - Group elements dynamically
- Cycle detection - In undirected graphs
- Kruskal's MST - Check if edge creates cycle
- Redundant connection - Find the extra edge
- Accounts merge - Group by shared emails
Union-Find is often simpler than DFS/BFS for connectivity problems, especially when edges are added dynamically. If you're building up connections one at a time, think Union-Find.