The Union-Find structure

Suppose you run a social network. Events keep arriving: A and B became friends, C and D became friends, B and C became friends. Between those events, someone asks: are A and D in the same group now? Being in the same group is transitive. If A—B, B—C and C—D all exist, then A and D belong to the same group even though they never met. This problem has a name: dynamic connectivity. Connections are added over time, and queries can arrive at any moment.

Answering that question needs only two operations, and a Union-Find structure provides exactly those two, no more.

Why not use graph traversal? You could store the edges and run a DFS or BFS from A each time, checking whether D is reachable (chapter 12 covers those). That works, but every query traverses the graph again at O(V+E), and the work is thrown away because new edges keep arriving. Union-Find is built for exactly this shape of problem. It is also called a disjoint set union structure, or DSU.

Everything a Union-Find owns is one array of integers, called parent. There are only two rules.

• parent[i] = j means the element directly above i is j. j is not necessarily the root. It may be one link in a longer chain.
• parent[i] = i means i points at itself, so i is a root and represents its whole set.

Why mark a root by making it point at itself? A root has no parent, so the slot has to hold something. Storing i itself costs no extra memory, needs no second array of flags, and makes the stopping test a single comparison: parent[x] == x. Every element, root or not, is handled by the same loop. That is why find is written this way: start at x and keep moving up until the element points at itself.

Now look at the array differently. Draw an arrow from every i to parent[i], and the array becomes a forest: several trees, one tree per set, each root representing its set. This is the second time in this book that an array plays the part of a tree. A heap encodes the parent-child links implicitly through the index arithmetic 2i+1 and 2i+2. Union-Find is more direct: it stores the parent of each node explicitly. In both cases the tree is only a logical shape. Physically there is one contiguous row of integers.

Try it below. Click two nodes and watch union call find on each side to reach the two roots, then attach one root under the other. Watch the parent array underneath at the same time and check that everything happening in the diagram is one number changing in the array. Then press Worst-case union to see what goes wrong.

The problem in the previous section is that the tree is too tall. The cost of find is the number of levels between a node and its root. Both optimizations aim at the same target, keeping the trees short, but they act at different moments and prevent different failures. Both matter, and it is worth being able to say what each one does.

find(x) walks from x up to the root anyway. Every node it passes on the way already has a known root by the time the walk finishes. So there is no reason to leave them pointing at intermediate nodes. After reaching the root, repoint every node on the path directly at the root.

The extra cost is small, because the walk was going to happen anyway and compression only adds a few assignments on the way back. The benefit is permanent: once a node has been compressed, later find calls on it take one step, until a later union puts a new root above it. Path compression is what prevents the same long path from being walked twice. On its own, without union by rank, it already brings the amortized cost down to O(log n).

Which root goes under which is not an arbitrary choice. Look at the height of the merged tree.

• Shorter tree under the taller one: the new height is max(taller, shorter + 1). While the shorter tree is strictly shorter, that is just the height of the taller tree, so the height does not grow.
• Taller tree under the shorter one: the new height is taller + 1, so a level is added for no reason.
• Two trees of equal height: whichever way you attach them, the result is one level taller. This is the only case where the height can grow.

So give every root a rank, a number that bounds the height of its tree. During union, the root with the smaller rank is attached under the root with the larger rank. If the two ranks are equal, attach either way and increase the new root's rank by 1. This alone keeps the height within O(log n), because a tree of rank r contains at least 2ʳ elements. Rank only rises when two trees of equal rank are merged, which at least doubles the size. The argument is the same one used for doubling a dynamic array. Some implementations use size instead of rank and attach the smaller set under the larger one. The bound is the same, and you get the size of each set as a by-product, which several problems need.

Path compression cannot prevent this problem, because it only runs during find and only fixes a path that has already been built. Union by rank stops the tall tree from being built at all. That is why they are not interchangeable.

Now check it in the lab. Turn on both switches and press Worst-case union again. The chain of 10 becomes a tree of depth 1.

Union-Find is one of the few structures worth writing from memory. No standard library provides it, so in a problem it always appears as a handwritten template plus a little modeling. The version below has both optimizations, plus two methods that problems ask for constantly: connected, which tests connectivity, and a count of the current number of components.

Three details in this template are used by problem after problem.

• union returns a boolean. false means the two elements were already in the same set, so nothing was merged. LC 684 finds the redundant edge with this return value, and so does the cycle test inside Kruskal's algorithm.
• count starts at n and only drops on a real merge. Each element begins as its own set, so there are n sets. A successful union replaces two sets with one, so the number falls by exactly 1. A union whose two sides already share a root merges nothing, so decrementing there would report fewer components than actually exist. This is why the check if (ra == rb) return false; comes before count--.
• Always find both roots before merging. The first line of union is never anything else. What union merges is two sets, not two individual elements.

None of the three standard libraries includes a Union-Find. C++ does not have one either. You will find it in Boost or in competitive programming template libraries. The reason is that the structure is small, and the useful details differ per problem, so writing thirty seconds of code beats a general API. What is worth comparing is therefore not the API but the choice of container.

One practical question comes up constantly: what if the keys are not the integers 0 to n−1? In LC 721 the keys are email addresses. In LC 128 they are arbitrary integers that may be negative or as large as 10⁹. The answer is the hash table from chapter 6: map each key to a fresh consecutive id, then use a normal array. The hash table translates, and Union-Find merges.

About 90% of the code in a Union-Find problem is the same template. What is actually being tested is modeling: translating the problem statement into "these are the nodes, this counts as an edge". Once that translation is done, only three patterns remain.

The problem: there are n cities, and isConnected[i][j] = 1 means i and j are directly connected. Being connected is transitive, and you must return the number of provinces, that is the number of components. The brute force approach: run a DFS from every unvisited city to mark its whole province, and count how many times you started one. That works and costs O(n²); chapter 12 covers it. The Union-Find view: every 1 in the matrix is an edge. Union cell by cell, let count fall from n, and the value left is the number of provinces. No visited array is needed.

The problem: a tree with n nodes should have exactly n−1 edges. One extra edge was added, so the graph now contains exactly one cycle. The edges are given in order, and you must return the extra edge. If more than one edge would work, return the one that appears last in the input.

The idea: a tree is a graph that is connected and has no cycle. Process the edges one at a time and union each one. Normally the two endpoints are in different sets, so the merge succeeds and the number of components drops by one. But if an edge's two endpoints already have the same root, a path between them already exists, and adding this edge closes a cycle. That edge is the redundant one.

Why does this give the last one automatically? The graph has exactly one cycle. Every edge that is not on the cycle joins two previously separate parts, so it never triggers the test. Among the cycle's edges, all but the last one in input order are added before the cycle is complete. So the edge that triggers the test is the only one that can, and it is the last edge of the cycle in input order. Below, the parent array is merged edge by edge, and the two endpoints of the conflicting edge are marked.

The problem: a grid holds only '1' for land and '0' for water. Land cells that touch horizontally or vertically form one island. Return the number of islands. The more common solution is DFS or BFS flooding, covered in the graph chapter. Here the same problem is solved from the Union-Find point of view: treat each land cell as a node, put an edge between adjacent land cells, and the number of components at the end is the number of islands.

Two things to get right. First, a 2D coordinate (r, c) has to be flattened into a single index id = r×cols + c before it can go into the parent array. This is the row-major layout from the array chapter. Second, each cell only has to look right and down. Its left and upper neighbors were already joined when those cells were processed, so checking them again is wasted work, the same reason 547 scans only the upper triangle.

count starts at the number of land cells, assuming each one is its own island, and drops by one on every successful union. Below, the 2×4 grid is flattened, scanned and merged, and count falls from 5.