Union-find
Union-find keeps track of which items are connected as links keep arriving. It merges two groups and tells whether two items share a group in almost constant time.
Each group is a tree, named by its root
Some problems keep merging groups and asking whether two items are in the same group: friend circles, computers joined by cables, pixels of one region, accounts that share an email. A search through the links after every change would cost O(n + m) each time. Union-find (also called a disjoint set union, or DSU) answers in almost constant time.
It stores each group as a tree, with one list: parent[x] is the item above x, and the item at the top, its own parent, is the group's root. Two operations do everything:
- find(x) climbs from x to its root. Two items are in the same group exactly when they have the same root.
- union(a, b) finds both roots and, if they differ, hangs one root under the other, merging the groups in one step.
The rule
Union-find answers "are a and b connected?" while links keep arriving. With union by rank and path compression, each operation costs nearly O(1) amortized, but it can only merge groups, never split them.
Union hangs one root under the other; find climbs to the root
Friends 0 and 3 were already connected through 1, so their union did nothing. The weak spot is the climb: if unions keep hanging a big tree under a single node, a tree can become a chain of n items, and find costs O(n).
Two small changes keep the trees almost flat
Union by rank keeps trees short. Each root keeps a rank, an upper bound on its tree's height. Hang the root of lower rank under the higher one, so the height doesn't grow; only when the ranks are equal does the new root's rank go up by one. (Union by size, comparing item counts instead, works as well.)
Path compression flattens trees as they are used. On its way back from the root, find points every item it passed straight at the root, so the next find from any of them takes one step.
Version | Cost of one find |
|---|---|
Plain | O(n) in the worst case: a chain |
Union by rank | O(log n): a tree of rank r holds at least 2ʳ items |
Path compression alone | O(log n) amortized |
Both | O(α(n)) amortized, where α grows so slowly it is at most 4 for any input that fits in a computer |
A link whose ends share a root closes a loop
Union-find also catches cycles as links arrive. Before adding a link, find both ends. Different roots: the link joins two groups. The same root: its ends were already connected, so the new link closes a loop. Here a tree got one link too many, and the first link that closes a loop is the extra one. The drawing shows the links; the number under each node is its parent in the union-find forest.
DFS from one end, checking whether the other is reachable, would cost O(n) per link. Union-find keeps the answer ready as the network grows, and the same check is the heart of Minimum spanning trees, where Kruskal's algorithm adds the cheapest links that don't close a loop.
3 questions
Remember this
- Union-find stores each group as a tree in one parent list; the root names the group.
- find climbs to the root; union hangs one root under the other.
- Union by rank and path compression together make each operation nearly O(1) amortized.
- A new link whose ends already share a root closes a loop.
Now solve some yourself
Only this topic 0 of 12 solved
- EasyFewest new roads to connect every city
- EasyFewest groups so no friends share one
- MediumCan these equal and not-equal rules all hold?
- MediumNumber and size of groups as roads are built
- MediumCheapest lessons so every employee can talk to every other
- MediumFewest cable moves to connect every computer
- MediumCount groups of friends from a matrix
- MediumSmallest string from equivalent letters
- MediumThe weakest road on a route between two cities
- HardThe extra link in a tree with directions
- HardGroups of strings one swap apart
- HardRemove the most links and keep both players connected
Mixed with topics you have practiced 0 unlocked
5 more once you have practiced Hash tables & maps, Basic sorting, Grid traversal. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next