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.

The single most common reason union-find shows up in an algorithms interview is Kruskal's algorithm, which finds a minimum spanning tree: the cheapest possible set of edges that connects every node in a weighted graph, with no cycles. The strategy is a greedy one, sorted by cost: look at every edge from cheapest to most expensive, and add it to the tree unless it would connect two nodes that are already connected, since that would create a cycle and add cost for no benefit. Union-find is exactly the tool that answers "are these two nodes already connected?" in essentially O(1), which is what makes the greedy approach efficient instead of needing a fresh graph traversal before every single edge decision.

Tracing it on a small 4-node graph (nodes 0 to 3) with edges 0-1 (weight 1), 0-2 (weight 4), 1-2 (weight 3), 1-3 (weight 2), and 2-3 (weight 5): sorted by weight, the edges are processed in the order 0-1, 1-3, 1-2, 0-2, 2-3. Processing 0-1 (weight 1): 0 and 1 are in separate groups, so union succeeds. Add the edge, running total 1. Processing 1-3 (weight 2): 1 and 3 are in separate groups, union succeeds. Add the edge, running total 3. Processing 1-2 (weight 3): 1 and 2 are in separate groups, union succeeds. Add the edge, running total 6, and all four nodes are now connected. Processing 0-2 (weight 4): find(0) and find(2) are already equal, since both were folded into the same group by the earlier unions, so union returns False and this edge is skipped. It would only create a cycle. Processing 2-3 (weight 5) is skipped for the same reason. The final minimum spanning tree uses edges 0-1, 1-3, and 1-2, for a total weight of 6, exactly n - 1 = 3 edges connecting all 4 nodes at the lowest possible total cost.

• -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), exactly as traced above.
• -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.