Union-Find: The Fellowship of the Sets

The Quest Begins (The "Why") I still remember the first time I saw LeetCode 323 “Number of Connected Components in an Undirected Graph”. I stared at the adjacency list, thought “I’ll just run a DFS from every node”, and coded it up in ten minutes. The solution passed the easy tests, but when the hidden test cases hit a graph with 10⁵ nodes and 10⁵ edges, my DFS started to choke—stack overflows, repeated visits, and a sinking feeling that I was brute‑forcing a problem that deserved a smarter tool. That night, after a few too many coffees, I stumbled upon a tiny comment in a discussion thread: “Union‑Find can do this in almost O(1) per operation”. My curiosity sparked like a power‑up in a retro arcade game. I had to know why this seemingly simple data structure could turn a nightmare into a breeze. The Revelation (The Insight) At its heart, Union‑Find (aka Disjoint Set Union, DSU) maintains a collection of elements partitioned into disjoint subsets. It supports two operations: Find(x) – returns the representative (root) of the set containing x . Union(x, y) – merges the sets containing x and y . The magic lies in two simple heuristics: Path Compression – when we walk up the tree to find a root, we make every node on that path point directly to the root. Future finds become flat, almost constant‑time. Union by Rank/Size – we always attach the smaller tree under the root of the larger one, keeping the overall tree shallow. Why does this give us near‑O(1) amortized time? Think of each Find as paying a small “tax” to flatten the path. The tax is paid only a few times per node before it becomes a direct child of the root. Over a sequence of m operations, the total work is bounded by O(m α(n)) , where α is the inverse Ackermann function—so slow‑growing it’s practically a constant for any realistic n . In plain English: every time we climb up, we leave a shortcut behind. The next climber benefits from that shortcut, and the structure keeps getting better. It’s like building