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:
