Union Find (DSU)
Answer "are these two nodes connected?" in near-O(1). Merge components dynamically as edges arrive. Detect cycles for free. Two arrays, two functions — one of the most practical data structures in competitive programming.
BFS/DFS connectivity check is O(V+E) per query. DSU answers the same question in O(α(n)) ≈ O(1) — and handles dynamic edge additions.
α(n) is the inverse Ackermann function — it grows so slowly it's less than 5 for any n you'll ever encounter. The magic comes from two optimisations: path compression (flatten on find) and union by rank (merge shorter tree under taller).
DSU: parent[] + rank[]
Two arrays. Two functions. Everything else is application.
parent[i]Stores the parent of node i. Initially parent[i]=i (each node is its own root). After unions, parent[i] points toward the component root. With path compression, most nodes point directly to the root.
parent = list(range(n)) # parent[i]=i → i is a root # parent[i]=j → j is parent of i
rank[i]Estimates the height of the subtree rooted at i. Used in union() to decide which root to attach under which. Only increases when merging two trees of equal rank. Prevents degenerate O(n) chains.
rank = [0] * n # rank[i]=0 → leaf or single node # rank grows slowly: ≤ log(n)
self.parent[x] = self.find(self.parent[x])— flattens the entire path to root on every find()
Union by rank: attach root with lower rank under root with higher rank — prevents O(n) degenerate chains
Together: O(α(n)) ≈ O(1) amortised — far better than either optimisation alone
The 3-Step Framework
Build DSU → union edges → query with find() or count.
parent = list(range(n)) sets every node as its own root. rank = [0]*n. count = n components. For 1-indexed problems (like Redundant Connection), use n+1. For grid problems (m×n), flatten to 1D: node = r*cols + c.
dsu = DSU(n) # 0-indexed dsu = DSU(n+1) # 1-indexed nodes # Grid flattening: node = r * cols + c dsu = DSU(rows * cols)
For each edge (u,v): call dsu.union(u,v). It returns True if merged (new connection), False if already connected (cycle for undirected graphs). For Kruskal-style problems: sort edges by weight first, then union in order.
for u, v in edges:
dsu.union(u, v)
# Cycle detection:
for u, v in edges:
if not dsu.union(u, v):
return [u, v] # redundant
# Kruskal (Path Min Effort):
edges.sort()
for w, u, v in edges:
dsu.union(u, v)
if dsu.connected(src, dst):
return wconnected(u,v) = find(u)==find(v). Use for: 'is there a path between u and v?', 'does adding this edge create a cycle?'. dsu.count gives the number of disjoint components at any point.
# Check connectivity:
if dsu.connected(src, dst):
return answer
# Count components:
return dsu.count
# Or manually:
return len({dsu.find(i)
for i in range(n)})Pattern Recognition
'connected components', 'cycle in undirected graph', 'union sets' → DSU.