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.

Every company has one chief executive. Employees report up the chain, and following the reports upward always ends at the chief executive, who identifies the company. To check whether two people work for the same company, you find each one's chief executive and compare. When two companies merge, the chief executive of one agrees to report to the other, and the two companies are now one.

• -A group is a set of elements, and its chief executive is its root.
• -find(x) is walking up the reporting line to the chief executive.
• -union(x, y) is a merger: one root starts reporting to the other.
• -connected(x, y) is asking whether the two chief executives are the same person.

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.

Start with 5 elements, 0 to 4, each its own parent, so parent is [0, 1, 2, 3, 4] and every rank is 0. Do three unions:

• -union(0, 1): the ranks are equal, so 1 goes under 0, and 0's rank becomes 1. Parent: [0, 0, 2, 3, 4].
• -union(2, 3): the same again, with 3 under 2 and 2's rank becoming 1. Parent: [0, 0, 2, 2, 4].
• -union(1, 3): the roots are 0 and 2, both of rank 1, so 2 goes under 0 and 0's rank becomes 2. Parent: [0, 0, 0, 2, 4].

Now call find(3). It walks 3 to 2 to 0, and path compression makes 3 point straight at the root, giving [0, 0, 0, 0, 4]. The next find(3) takes one hop. Element 4 never merged, so connected(0, 4) is False, while connected(0, 3) is True.

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 set of edges that connects every node in a weighted graph, with no cycles.

The strategy is greedy. Consider every edge from cheapest to most expensive, and add it to the tree unless it would join two nodes that are already connected, since that would create a cycle and add cost for no benefit. Union-find answers are these two nodes already connected? in essentially O(1), which is what keeps the greedy approach efficient instead of needing a graph traversal before every edge.

Trace it on a 4-node graph (nodes 0 to 3) with edges 0-1 (weight 1), 0-2 (4), 1-2 (3), 1-3 (2) and 2-3 (5). Sorted by weight, the edges are processed in the order 0-1, 1-3, 1-2, 0-2, 2-3:

• -0-1 (weight 1): 0 and 1 are in separate groups, so the union succeeds. Keep the edge, running total 1.
• -1-3 (weight 2): separate groups, so the union succeeds. Keep it, running total 3.
• -1-2 (weight 3): separate groups, so the union succeeds. Keep it, running total 6. All four nodes are now connected.
• -0-2 (weight 4): find(0) and find(2) are already equal, so union returns False. Skip it, since it would only create a cycle.
• -2-3 (weight 5): skipped for the same reason.

The minimum spanning tree uses edges 0-1, 1-3 and 1-2, total weight 6: exactly n - 1 = 3 edges connecting all 4 nodes at the lowest possible 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.