Union Find
01 / The one-sentence essence
Maintain a partition ofNelements into disjoint components; collapse two components into one in near-constant time. A forest of trees where the root is the component identity, and everyfindshortens the tree it touches.
Problemcount connected components via DSUNodes6Edges5
Start: 6 nodes, each its own component. Process edges one by one — each union merges two trees.
step
0 / 16
edge
—
action
init
components
6
0 / 16
02 / The pattern signature
# two arrays + two operationsparent[i] ← i # everyone is their own rootsize[i] ← 1 def find(x):while parent[x] ≠ x:parent[x] ← parent[parent[x]] # compressx ← parent[x]return x def union(a, b):ra, rb ← find(a), find(b)if ra == rb: return Falseif size[ra] < size[rb]: ra, rb ← rb, raparent[rb] ← ra # smaller under largersize[ra] += size[rb]return True
03 / When to recognize this pattern
"connected components"
Count or query whether a set of elements falls into the same group. Equivalence relation: reflexive, symmetric, transitive. If you'd naively run BFS/DFS from every node, suspect Union-Find.
"merge two groups"
The problem incrementally combines clusters — friends becoming friends-of-friends, edges added one at a time, accounts that share an email. The structure of the merges doesn't matter, only the membership.
"cycle detection in undirected graph"
Add edges one at a time; the edge that connects two already-in-the-same-component nodes closes a cycle. Used in Kruskal's MST and LC 684.
"offline queries"
When you can process queries in a batch (instead of online), DSU can answer "is x connected to y after these k operations?" in near-constant time per query.
04 / Common pitfalls
Skipping the two optimizations.
A DSU without path compression OR union-by-size/rank degrades to
O(N) per operation in the worst case (a left-leaning chain). With either optimization you get O(log N); with both you get α(N). Always include both — the code is ten lines either way.Forgetting to find before comparing.
To check "are a and b connected?" you must compare
find(a) == find(b), not parent[a] == parent[b]. The latter checks immediate parents — which only works after a global flatten.Mutating during iteration.
Path compression rewrites the
parent array during find. If you iterate parent directly while calling find on each entry, you'll see partial updates. Either snapshot first, or only call find when you genuinely need a fresh root.05 / Go practice — on LeetCode
medium20
01Longest Consecutive Sequence— LC 128→02Surrounded Regions— LC 130→03Number of Islands— LC 200→04Graph Valid Tree— LC 261→05Number of Connected Components in an Undirected Graph— LC 323→06Evaluate Division— LC 399→07Number of Provinces— LC 547→08Redundant Connection— LC 684→09Accounts Merge— LC 721→10Sentence Similarity II— LC 737→11Most Stones Removed with Same Row or Column— LC 947→12Satisfiability of Equality Equations— LC 990→13The Earliest Moment When Everyone Become Friends— LC 1101→14Connecting Cities With Minimum Cost— LC 1135→15Smallest String With Swaps— LC 1202→16Number of Operations to Make Network Connected— LC 1319→17Detect Cycles in 2D Grid— LC 1559→18Min Cost to Connect All Points— LC 1584→19Path With Minimum Effort— LC 1631→20Minimize Hamming Distance After Swap Operations— LC 1722→
hard11
01Number of Islands II— LC 305→02Redundant Connection II— LC 685→03Couples Holding Hands— LC 765→04Swim in Rising Water— LC 778→05Bricks Falling When Hit— LC 803→06Minimize Malware Spread— LC 924→07Largest Component Size by Common Factor— LC 952→08Optimize Water Distribution in a Village— LC 1168→09Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree— LC 1489→10Rank Transform of a Matrix— LC 1632→11Checking Existence of Edge Length Limited Paths— LC 1697→