cf.completefrontend
GRAPHS · CORE

Union-find (disjoint set union)

Keep track of which items are in the same group while groups keep merging, answering "same group?" almost instantly.

Time O(α(n)) per operationSpace O(n)9 practice problemsStep-through picture

The idea

Union-find, also called disjoint set union, keeps items in groups that never overlap. It supports two operations. union(a, b) merges the group of a with the group of b. find(x) returns a representative of x's group, called its root. Two items are in the same group exactly when they have the same root.

Each group is stored as a small tree using one array, parent. Every item points to a parent, and the root points to itself. To find the root, follow parents until an item points to itself. To merge two groups, point one root at the other.

Two small tricks keep the trees almost flat. Union by size attaches the smaller tree under the bigger one. Path compression makes items point closer to the root while find walks up. With both, each operation takes nearly constant time, even for millions of items.

An everyday example

Company mergers

Every small company starts as its own boss. When two companies merge, the boss of the smaller company starts reporting to the boss of the bigger one. To learn which company an employee finally belongs to, you follow the chain of bosses to the top. After doing that once, the employee just writes down a boss much closer to the top, so the next lookup is quicker.

How the example maps to the code
In the exampleIn the code
Each employee's direct bossparent[x]
The top boss of a companyThe root, where parent[x] === x
Following the chain of bossesfind(x)
Two companies mergingunion(a, b)
The smaller company reports to the biggerComparing size[rootA] and size[rootB]

From the slow way to union-find (disjoint set union)

  1. Start with the obvious way: give every item a group label, label[x]. Asking "same group?" is one comparison, label[a] === label[b]. But merging two groups means rewriting the label of every item in one of them. That's up to n writes per merge, and about n² writes for n merges: a trillion for a million items.
  2. Notice that nobody ever asks for the full list of a group's members. We only need one name that all members agree on. So an item doesn't have to store the name itself. It can store a pointer to another member of its group, its parent, and the name is wherever the pointers stop: the root. Merging two groups is now one write: point one root at the other.
  3. That alone can build long chains. Merge item 1 under 0, then 2 under 1, then 3 under 2, and find(3) walks through every item. The first fix is union by size: always hang the smaller tree under the root of the bigger one. An item only moves one level further from its root when its group at least doubles, so no item is ever more than log₂ n steps from its root.
  4. The second fix is path compression. While find walks up, it points each item at its grandparent, so the path it just walked becomes about half as long for next time. Together the two fixes keep every tree nearly flat. Two arrays, parent and size, plus a find that halves paths and a union that links roots by size: that is union-find.

How it works

  1. Start with parent[i] = i for every item, so each item is its own group, and size[i] = 1.
  2. find(x): while x is not its own parent, point x at its grandparent (path compression) and move up.
  3. When x points to itself, it is the root: return it.
  4. union(a, b): find rootA and rootB. If they are equal, the items are already together: return false.
  5. Make rootA the bigger group by swapping if needed, then set parent[rootB] = rootA.
  6. Add size[rootB] to size[rootA] and return true.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class UnionFind {
  2. constructor(n) {
  3. this.parent = Array.from({ length: n }, (_, i) => i);
  4. this.size = new Array(n).fill(1);
  5. }
  6. find(x) {
  7. while (this.parent[x] !== x) {
  8. this.parent[x] = this.parent[this.parent[x]];
  9. x = this.parent[x];
  10. }
  11. return x;
  12. }
  13. union(a, b) {
  14. let rootA = this.find(a);
  15. let rootB = this.find(b);
  16. if (rootA === rootB) return false;
  17. if (this.size[rootA] < this.size[rootB]) [rootA, rootB] = [rootB, rootA];
  18. this.parent[rootB] = rootA;
  19. this.size[rootA] += this.size[rootB];
  20. return true;
  21. }
  22. }

How fast it is

TimeO(α(n)) per operation
Extra memoryO(n)

With union by size and path compression, the trees stay so flat that each find or union takes nearly constant time. The parent and size arrays hold one number per item.

  • Best caseO(1)

    find is called on a root, or on an item that already points straight at its root, such as item 5 in the trace.

  • Average caseO(α(n))

    Any long mix of union and find calls. Spread over the whole sequence, each call costs about α(n) steps, which is at most 4 in practice.

  • Worst caseO(log n)

    One find on the deepest item of a tree that path compression hasn't touched yet. Merging 1,024 items in equal-sized pairs, round after round, builds a tree 10 levels deep.

Common mistakes

  • Comparing parent[a] === parent[b] instead of find(a) === find(b). Two items can be in the same group with different direct parents.
  • Setting parent[a] = b instead of linking the roots. That can split a away from the rest of its old group.
  • Skipping union by size and path compression. Long chains form, and each find can take O(n).
  • Updating size on the wrong root, or reading size[x] for an item that is not a root.

When to use it

Look for these clues in a problem:

  • Items get connected over time and you keep asking whether two items are connected.
  • You need the number of separate groups, or the size of each group, as edges are added.
  • The question asks which edge first closes a loop, or when everything becomes connected.
  • You are building a minimum spanning tree with Kruskal's algorithm.
  • Equalities like a == b must be grouped before checking a != c rules.

Check yourself

Answer each one in your head first, then open it.

Why compare find(a) === find(b) and not parent[a] === parent[b]?

Two items in the same group can have different direct parents, like items 3 and 6 in the trace after union(3, 2). Only their roots must match.

Why does union change parent[rootB] and never parent[b]?

Moving b alone would pull it away from the rest of its old group. Moving the root carries the whole group along, because every member's chain ends at that root.

With union by size only, how far can an item of a 1,000-item group be from its root?

At most 9 steps, because an item gets one step deeper only when its group at least doubles, and 2¹⁰ = 1,024 is more than 1,000. A tenth step would need at least 1,024 items.

What does it mean when union returns false?

The two items were already connected, so the new connection adds nothing. In a graph, that edge closes a loop.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 9 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The structure keeps one rule: every item's chain of parents ends at exactly one root, and two items share a root exactly when a series of successful union calls joined them. At the start, every item is its own root and its own group, so the rule holds.

Both operations keep the rule. union only changes the parent of a root, rootB, and points it at another root, rootA. Every item whose chain ended at rootB now ends at rootA, and no other chain changes. Path compression sets parent[x] to its grandparent, which sits on the same chain, so the root at the end doesn't change either.

Every find stops, because the parent pointers never form a loop: only a root ever gets a new parent, and it's pointed at the root of a different tree. Union by size keeps each tree at most log₂ n tall, since an item gets one step deeper only when its group at least doubles, and a group can double at most log₂ n times. Path compression only shortens paths. A careful analysis of both together gives the α(n) bound, where α is the inverse Ackermann function, below 5 for any input that fits in memory.

Going deeper

3 more ideas

Why the root names the group

Every item's chain of parents ends at exactly one root, and union only ever changes the parent of a root. So all items in a group lead to the same root, and items in different groups lead to different roots. Comparing roots is therefore the same as comparing groups.

Why it is so fast

Union by size alone keeps every tree at most log n tall, because an item only moves one level deeper when its group at least doubles in size. Adding path compression makes the cost per operation grow so slowly (the inverse Ackermann function, written α(n)) that it is below 5 for any input that fits in memory. In practice, treat it as constant time.

What it can't do

Union-find only merges. It can't split a group back apart or remove an edge. If edges are removed over time, one trick is to process the events in reverse, so removals become additions.

Work it by hand

Every step in a table, with why

Seven items, seven union calls. The last call finds the two items already together, and its find shortens a path on the way.

new UnionFind(7), then union(4, 5), union(0, 6), union(6, 2), union(5, 3), union(1, 3), union(3, 2), union(2, 1)

StepCallrootArootBparent afterWhat happensWhy
1union(4, 5)45[0, 1, 2, 3, 4, 4, 6]Link: parent[5] = 4Both items are roots of groups of size 1. No swap is needed, so 5 hangs under 4 and size[4] becomes 2.
2union(0, 6)06[0, 1, 2, 3, 4, 4, 0]Link: parent[6] = 0Two more groups of size 1 merge. size[0] becomes 2.
3union(6, 2)02[0, 1, 0, 3, 4, 4, 0]Link: parent[2] = 0find(6) walks one step, from 6 to its root 0. Group 0 has 2 items and group 2 has 1, so 2 hangs under 0 and size[0] becomes 3.
4union(5, 3)43[0, 1, 0, 4, 4, 4, 0]Link: parent[3] = 4find(5) returns 4. Group 4 is bigger, so 3 joins it and size[4] becomes 3.
5union(1, 3)41[0, 4, 0, 4, 4, 4, 0]Swap, then parent[1] = 4find(1) is 1 and find(3) is 4. Since size[1] = 1 is less than size[4] = 3, the roots swap, so the small group goes under the big one. size[4] becomes 4.
6union(3, 2)40[4, 4, 0, 4, 4, 4, 0]Link: parent[0] = 4The group of 4 items meets the group of 3. Root 0 goes under root 4, and size[4] becomes 7: everything is one group now.
7union(2, 1)44[4, 4, 4, 4, 4, 4, 0]Same root: return falsefind(2) sees parent[2] = 0, which isn't a root, so it sets parent[2] = parent[0] = 4 and reaches root 4. find(1) is also 4, so nothing is merged.

All 7 items share root 4, and the last call returns false because 2 and 1 were already connected through earlier merges. Item 6 still points at 0, two steps from the root; the next find(6) will set parent[6] = 4.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Union-find (disjoint set union)O(α(n))O(n)Connections keep arriving and you ask "same group?" many times. The time is per operation, spread over the whole sequence.
BFS or DFS for each questionO(V + E)O(V + E)You ask only once or twice, or edges are also removed, so a fresh search on the current graph is simpler.
Group label arrayO(n)O(n)Merges are rare and you need each group's member list. Each merge relabels a whole group, but each question is one comparison.

Extra memory: O(n): the parent and size arrays hold one number per item. find is a loop, not recursion, so it uses no call stack.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Union-find (disjoint set union) and the other approaches, on a scale where each line up is 10 times more steps.
  • Union-find (disjoint set union) O(α(n))
  • BFS or DFS for each question O(V + E)
  • Group label array O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Union-find (disjoint set union)111
BFS or DFS for each question202,0002 million
Group label array101,0001 million

Inputs that need care

5 tricky inputs
union(3, 3): an item with itself
Both find calls return the same root, so it returns false and changes nothing.
union(a, b) when a and b are already in one group
It returns false. Callers use this: Kruskal's algorithm skips that edge, and a cycle check reports it as the edge that closes a loop.
Items that are strings, such as email addresses
parent is an array indexed by number. Give each string an index with a Map the first time you see it, or store parent and size in Maps instead.
Reading size[x] when x isn't a root
The value is out of date, because only roots are updated. Read size[find(x)] to get the size of x's group.
Counting the groups
Start a counter at n and subtract 1 every time union returns true. In the trace, 6 successful unions on 7 items leave 1 group.

Variations and follow-ups

Twists interviewers add

Union by rank

Instead of size, store rank, an upper bound on each tree's height, and hang the lower tree under the higher one. Only when two ranks are equal does the new root's rank go up by 1. It gives the same bounds as union by size, but size is more useful because it also answers "how big is this group?".

Full path compression

The recursive version find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } points every item on the path straight at the root in one call. It flattens more than halving, but its recursion can be as deep as the tree on the first call.

Union-find with weights

Store, for each item, a number relative to its parent, such as "a is 3 times b" or "a and b are on opposite teams". find adds or multiplies the numbers along the path while compressing it. This answers questions like "what is a / c?" or "is this split into two teams still possible?" as facts arrive.

Undo instead of compression

Union-find can't split groups, but it can roll back. Skip path compression, keep union by size, and push every change onto a stack, so the latest union can be undone. This is used when edges are added and later removed in last-in, first-out order.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from words like "connected", "same group", "merge accounts", "which edge makes a loop", or "the earliest time everyone is connected", especially when the connections arrive one by one.
  • Say the rule out loud: "every item points toward its group's root, and two items are together exactly when their roots match". Then draw the parent arrows for three or four unions; interviewers follow pictures faster than code.
  • Test by hand: a union of two items already together, a union that needs the swap, and a find on an item two levels deep, checking that parent changes the way path compression says.
  • The usual follow-up is "what's the time complexity?". Answer: nearly constant per operation, O(α(n)), because union by size keeps trees at most log n tall and path compression flattens them further. Without both, a chain can make find cost O(n).

Where frontend code uses it

The same idea in real UI code
  • Merging duplicate user or customer records that share an email or phone number into one profile.
  • Grouping items that touch or overlap in a design tool or canvas editor, such as shapes snapped together into one connected group.
  • Image tools that label connected regions of pixels in one pass, merging labels when two regions turn out to touch.

Related algorithms