Union-Find: Tracking Connected Groups

Some problems boil down to a single repeated question: "are these two elements part of the same group?" - friends in the same social circle, computers on the same network segment, cities connected by some path of roads. You could answer this with a graph traversal (BFS/DFS, coming up in Tier 6) every single time you ask, but if the groups themselves are also changing - new connections being added over time - re-running a full traversal on every query gets expensive fast. Union-Find (also called Disjoint Set Union) is a structure purpose-built for exactly this: efficiently merging groups together and efficiently answering "same group?" as you go.

The core idea: each element points to a "parent," and following parent pointers upward eventually reaches a representative root for the whole group. Initially, every element is its own parent (n separate groups of size 1). `find(x)` walks up parent pointers until it hits an element that is its own parent - the root, which serves as the group's unique identifier. `union(x, y)` finds each one's root and points one root at the other, merging the two groups into one. Done naively, though, repeated unions can build a long chain, degrading `find` toward O(n) - exactly the same skewed-tree problem that motivated balanced BSTs.

Path compression is a small change with an outsized effect: while `find` is walking up to the root anyway, make every node along the way point directly at that root, instead of at its old, possibly-distant parent. The next `find` on any of those nodes then takes just one hop. This flattens the tree over time as more finds are performed.

The second optimization controls how trees get taller in the first place: track an approximate "rank" (roughly, tree height) per root, and when merging two groups, always attach the shorter tree under the taller tree's root, rather than an arbitrary choice. This keeps the resulting tree from growing taller than necessary, which keeps future `find` calls cheap even before path compression has a chance to kick in.

• -Kruskal's algorithm for a minimum spanning tree: process edges cheapest-first, and use union-find to skip any edge that would connect two nodes already in the same group (which would create a cycle).
• -Cycle detection in an undirected graph: while adding edges one at a time, if `union(u, v)` ever returns false, u and v were already connected - this new edge closes a cycle.
• -Network/account connectivity: incrementally merging "these two accounts are linked" facts and instantly answering "are these two the same person?" without re-scanning everything.