Union-Find (Disjoint Sets)
Merge groups and ask 'same set?' in near-constant time. The quiet workhorse of connectivity and cycle problems.
Union-Find tracks groups as they merge. It answers two operations very quickly: “Which group is this item in?” and “Merge these two groups.” That is the exact shape of connectivity problems where edges arrive and components collapse over time.
DFS and BFS are excellent when you have the whole graph and want to explore it. Union-Find is better when the work is edge-centric: process connections one by one, merge components, and ask whether two nodes were already connected.
The mental model
Each item points to a parent. A root points to itself and represents the whole set. find(x) follows parent pointers to the root; union(a, b) connects the two roots if they differ.
The two optimizations are what make the structure fast:
- Path compression — after finding a root, make every node on that path point directly to the root.
- Union by rank or size — attach the smaller or shallower tree under the larger one so parent chains stay short.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return TrueWith both optimizations, operations are effectively constant time in practice: near-O(1) amortized, formally O(alpha(n)) where alpha is the inverse Ackermann function. It grows so slowly that for interview-scale inputs it behaves like a small constant.
Pattern recognition
Variations
Worked problems
All three problems use the same DSU class. The only difference is how the input is converted into union operations.
Number of Connected Components in an Undirected Graph
Given n labeled nodes and an edge list for an undirected graph, return how many connected components the graph has.
Approach. Start with n isolated components. For each edge, union its two endpoints. If the union actually merges two different roots, decrement the component count. Edges inside an existing component do not change the count.
Show solution
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def count_components(n, edges):
dsu = DSU(n)
components = n
for a, b in edges:
if dsu.union(a, b):
components -= 1
return componentsComplexity. O((n + e) alpha(n)) time for e edges and O(n) space. The inverse Ackermann factor is effectively constant.
Number of Provinces
Given an adjacency matrix where is_connected[i][j] says whether two cities are directly connected, return the number of connected city groups.
Approach. Treat each city as a DSU node. Only scan one triangle of the matrix because the graph is undirected and the matrix is symmetric. Every 1 merges two cities into the same province.
Show solution
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def find_circle_num(is_connected):
n = len(is_connected)
dsu = DSU(n)
provinces = n
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j] == 1 and dsu.union(i, j):
provinces -= 1
return provincesComplexity. O(n^2 alpha(n)) time because the matrix has O(n^2) entries, and O(n) space for the DSU arrays.
Redundant Connection
Given edges for an undirected graph that started as a tree and then received one extra edge, return the edge that creates the cycle.
Approach. In a tree, every new edge should connect two previously separate components. Process edges in order and union their endpoints. The first edge whose endpoints already have the same root is redundant because it closes a cycle.
Show solution
class DSU:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
self.parent[ra] = rb
elif self.rank[ra] > self.rank[rb]:
self.parent[rb] = ra
else:
self.parent[rb] = ra
self.rank[ra] += 1
return True
def find_redundant_connection(edges):
dsu = DSU(len(edges))
for a, b in edges:
if not dsu.union(a, b):
return [a, b]
return []Complexity. O(e alpha(n)) time and O(n) space. The failed union is the signal that the new edge connects two nodes already in the same component.