The Quest Begins (The "Why")
I still remember the first time I stared at a LeetCode problem that asked me to count the number of islands in a grid. My initial instinct? Run a BFS/DFS from every unvisited land cell, mark everything reachable, and repeat. It worked, but each query felt like I was re‑exploring the same territory over and over again—like walking the same hallway in a dungeon every time I wanted to open a new door.
Then a friend tossed me another problem: “Given a list of friendships, tell me if two people are in the same social circle.” Again, the naive solution was to rebuild the whole graph for every query. I felt like I was stuck in a grind‑fest, repeating the same low‑level work while the real challenge—understanding the structure of the connections—remain.
That frustration sparked a question: Is there a way to remember what we’ve already discovered about connectivity, so future queries are instant? The answer, as many of you have guessed, lives in a humble but mighty data structure called Union‑Find (also known as Disjoint Set Union, DSU).
The Revelation (The Insight)
