AdvancedGraphs
Union-Find: are these connected?
Give every node a parent pointer; union joins two groups' roots. With path compression, each operation is nearly O(1).
The idea
Union-Find keeps disjoint groups. find(x) follows parent pointers to the group's root; union(a, b) points one root at the other. Two nodes are connected exactly when they share a root.
Path compression (point nodes straight at the root as you find it) and union by size keep the trees flat, so long chains never form.
Worked example
Redundant Connection: edges (1,2), (1,3), (2,3)
- union 1–2 → one group; union 1–3 → one group {1,2,3}
- edge 2–3: find(2) == find(3) already → this edge makes a cycle → it's the redundant one.
In code (Python)
class UnionFind:
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]] # compress
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
self.size[ra] += self.size[rb]
return TrueNearly O(1) per operation (inverse Ackermann).
How to spot it
- “connected components”, “redundant edge”, merging groups, Kruskal's minimum spanning tree.
Common mistakes
- Comparing parents instead of roots.
- Skipping both optimizations and getting O(n) chains.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →