Day 20 — Union Find (DSU)

Some problems aren’t really algorithm problems — they’re bookkeeping problems. “Are these two people in the same friend group?” “How many connected components are there?” “If I add this edge, does it close a cycle?” The hard part isn’t the logic; it’s tracking partitions of a set that keep merging as the input streams in.

Disjoint Set Union (DSU) — also called Union Find — is the data structure built for exactly this. Thirty lines of code, two operations (find and union), and with two tiny optimizations the amortized cost per operation is less than the inverse Ackermann function — effectively constant for any input you’ll ever see.

The leverage is wild. Once you know DSU, problems that look like graph search collapse to “scan the edges, union the endpoints, done.” Kruskal’s MST. Cycle detection. Offline connectivity queries. Equivalence classes. Even some grid problems.

What you’ll learn today

• The disjoint set abstraction — what it tracks and what operations it supports
• The naive tree representation and why it can degrade to O(n)
• The two killer optimizations: union by rank (or by size) and path compression
• The inverse Ackermann analysis — why amortized O(α(n)) ≈ O(1)
• Applications: Kruskal’s MST, cycle detection, connected components, equivalence classes
• Eight interview classics where DSU is the single best tool

Roadmap

1. Introduction — the disjoint-set abstraction, the partition view, and the two operations every DSU supports.
2. The DSU Template — the parent-array representation, naive find and union, and the worst-case O(n) chain problem we’ll need to fix.
3. Optimizations — union by rank, path compression, and the amortized analysis that lands at O(α(n)) per operation.
4. Applications — Kruskal’s MST recap, cycle detection in undirected graphs, connected-components counting, and the “weighted union find” extension for distance / parity tracking.
5. Basic Questions — warm-ups: hand-trace union, identify the find-chain, count connected components.
6. Practice Questions — eight interview problems covering every flavor of the pattern.

DSU pairs naturally with graph problems: it’s the workhorse for Day 22 — MSTs and shows up in Day 23 — Topological Sort. It also complements Day 10 — BFS/DFS — for dynamic connectivity under edge additions, DSU is faster; for queries that require explicit traversal (shortest path, all paths), BFS/DFS wins.

Coming up: Day 21 — Shortest Paths, where BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall split the shortest-path landscape four ways.