Algorithms · Union-find

Union-find

The forest of sets, find and union, why the trees degenerate, path compression, union by size, why together they are near-constant, and what the structure cannot do.

Updated 2026-09-21

On this page

Union-find answers one question — "are these two things in the same group?" — while groups keep merging underneath you. It is barely twenty lines of code, it is almost as fast as an array lookup, and the two tricks that make it fast are both a single line. It is probably the highest ratio of usefulness to code size in this whole subject.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

The problem

You have a pile of items and a growing list of statements like "these two are connected". At any moment you need to answer: are these two in the same group?

You could rebuild the answer each time with a traversal, but that is a full O(V + E) pass per query, which is far too slow when there are millions of queries mixed in with millions of merges. What you want is a structure where both operations are effectively free:

find(x) — which group is x in?
union(x, y) — merge the groups containing x and y.

Note the shape of the problem: groups only ever merge, never split. That restriction is what makes such a fast structure possible, and it is the main thing to remember about when union-find does and does not apply.

The forest

Represent each group as a tree. Every item points at a parent; the item at the top points at itself and is the root. The root is the group's name — not because it is special, but because it is the one thing everybody in the group can agree on.

Figure 2. Sets as trees. The shape of a tree carries no meaning — only which root you end at matters, which is why the structure is free to rearrange itself.

That last point licenses everything that follows. Since only the root identity matters, the algorithm may reshape trees however it likes, and the two optimisations below are exactly that.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))       # everyone starts as their own root

    def find(self, x):
        while self.parent[x] != x:         # walk up to the root
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                   # already together
        self.parent[rb] = ra               # hang one root under the other
        return True

That works and it is correct. The problem is speed: nothing stops the trees becoming chains.

Why it degenerates

Union always hangs the second root under the first. So union(1,2), union(2,3), union(3,4) and so on builds a single line of nodes, and find on the deepest one walks the entire list.

Figure 3. Path compression. The single find that had to walk the chain repays the cost by flattening it, so every later find on any of those nodes is one hop.

Fix one: path compression

You just walked from a node to the root, so you know the root. Before returning, point every node you passed directly at it. The walk was going to happen anyway; the flattening is nearly free.

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:          # second pass: repoint everything
            self.parent[x], x = root, self.parent[x]
        return root

Or recursively, which is shorter and does the same thing:

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # set parent to the root on the way out
        return self.parent[x]

The effect is that queries pay for future queries. An expensive find happens once; every subsequent one on that part of the tree is immediate. On its own this is already good enough for most real workloads.

Fix two: union by size

Compression repairs bad shapes after the fact. The second fix stops them forming: when merging, always hang the smaller tree under the larger one.

The reasoning is neat. Attaching a small tree under a big one leaves the big tree's depth unchanged and only deepens the small one's nodes — and any node whose depth increases must be in a tree at most half the size of the new combined tree. A node's depth can therefore only increase when the set it belongs to doubles, and a set can only double about log n times. So depth is bounded by log n, even with no compression at all.

    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n                     # how many items in each root's tree

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:       # make ra the bigger one
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

A common variant tracks rank — an upper bound on height — instead of size. Both work. Size is more useful because "how big is this group" is often wanted anyway, and it is harder to get wrong.

Watch out

Size and rank are only meaningful at a root. Reading size[x] for a node that is not a root gives a stale number from when it was one. Always find first, then read the size of the root.

Why both, and how fast it ends up

Each fix covers the other's weakness. Union by size prevents tall trees from being built; path compression flattens whatever height does appear. With both, the amortised cost per operation is α(n) — the inverse Ackermann function, which is below 5 for any input that could physically exist.

Version	Cost per operation	In practice
Neither fix	O(n) worst case	Degenerates to a linked list; unusable on adversarial input
Path compression only	Near-constant amortised	Fine for almost everything real
Union by size only	O(log n)	Predictable, no amortisation needed
Both	O(α(n)), effectively constant	The standard implementation; treat it as O(1)

The honest summary is that α(n) is a theoretical curiosity: it is 4 for inputs far larger than the number of atoms in the observable universe. In any complexity analysis you can write "effectively constant" and move on. What matters practically is that both fixes are one line each, so there is no reason to omit either.

What it cannot do

The restriction that makes union-find fast also bounds what it is for, and knowing the edges saves you from forcing it somewhere it does not fit.

It cannot split. There is no un-union. Once merged, always merged. Deleting an edge from a graph and asking whether things are still connected is not a union-find problem, because the structure has thrown away which merges came from which edges.

Three usual ways around it, in order of how often they work:

Reverse the problem. If all the deletions are known in advance, process them backwards — deletions in reverse are additions, which union-find handles perfectly. This offline trick solves a surprising number of "connectivity after removals" problems.
Rollback. Keep a log of each union's changes and undo them in reverse. This requires dropping path compression, since compression makes changes that cannot be cleanly reversed, so cost rises to O(log n) per operation.
Rebuild. If deletions are rare, recompute from scratch when one happens.

It knows the group, not the shape. Union-find can tell you two nodes are connected but not by what path, how far apart they are, or what lies between. If the question involves distance or route, you need a traversal — that is what BFS and Dijkstra are for.

Where it is used

In the wild

Kruskal's minimum spanning tree. Sort the edges by weight and add each one only if its endpoints are in different sets. The "would this create a cycle?" test is just a find comparison, and this is the classic application.
Connected components in a stream. When edges arrive over time and questions arrive between them, union-find answers each immediately — where re-running a traversal per query would not finish.
Grids and percolation. Merge neighbouring open cells; adding one virtual node joined to the whole top row and another to the bottom row turns "does a path exist from top to bottom" into a single find comparison.
Record deduplication. Each "these two records are the same person" becomes a union, and the final groups are the merged identities.

The virtual-node trick deserves a second look, because it generalises: when you want to ask about a whole set of nodes at once, add a single fake node connected to all of them and the question collapses to one query.

Recap

Union-find answers "are these two in the same group?" while groups keep merging, without re-running a traversal for every query.
Each set is a tree; every node points at a parent and the root points at itself. The root is the group's name.
find walks to the root; two items are together exactly when their roots match. union points one root at the other.
The shape of a tree carries no meaning, only which root you reach — which is why the structure is free to rearrange itself.
The naive version degenerates: repeated unions can build a chain, and find then walks the whole thing.
Path compression: after walking to the root, point every node you passed directly at it, so later finds are one hop. The walk already happened, so it is nearly free.
Union by size: always hang the smaller tree under the larger. A node's depth can only grow when its set doubles, so depth stays below log n.
Together they give O(α(n)) amortised — under 5 for any real input, so treat it as constant.
Size and rank are only valid at a root; always find first, then read the root's size.
It cannot split. Edge deletion is not a union-find problem — reverse the operations offline, use rollback without compression, or rebuild.
It knows membership, not structure: no paths, no distances. Those need a traversal.
Kruskal's MST, streaming connected components, grid percolation with a virtual node, and record deduplication are the standard uses.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail that shows depth.

What problem does union-find solve, and why not just use a traversal?

It answers "are these two in the same group?" while groups merge over time. A traversal costs a full O(V + E) pass per query, which is hopeless when millions of queries are interleaved with millions of merges.

Union-find makes both the query and the merge effectively constant time.
The key restriction is that groups only merge, never split.
That restriction is exactly what makes such a fast structure possible.

If the problem involves removing connections, union-find is probably the wrong tool, and recognising that early saves a lot of wasted effort.

How are the sets represented?

As a forest: every item stores a parent index, a root stores itself, and the root serves as the group's identifier. Two items are in the same group exactly when they reach the same root.

The root is not special in any way beyond being the agreed name for the set.
The tree's shape carries no information, so the algorithm may reshape it freely.
A single parent array is enough for the whole structure.

That the shape is meaningless is what licenses both path compression and union by size.

Why does the naive version become slow?

Because union always attaches one root under the other without considering size, a sequence like union(1,2), union(2,3), union(3,4) builds a single chain, and find on the deep end walks every node — O(n) per operation.

It is not a rare pathological case; sequential merges produce it naturally.
Both fixes attack it from different directions: one prevents chains, the other flattens them.
Each fix is a single line, so there is no reason to ship the naive version.

This is a good example of a correct implementation whose performance is unusable without a small structural insight.

Explain path compression.

After find walks from a node up to the root, it makes a second pass pointing every node it visited directly at the root — so subsequent finds on any of them take one step.

The walk was necessary anyway, so the flattening costs almost nothing extra.
The recursive form does it naturally by reassigning the parent as the calls unwind.
Queries therefore pay for future queries, which is why the cost is amortised rather than worst case.

On its own it is already fast enough for most real workloads, even without union by size.

Explain union by size, and why it bounds the depth.

Always attach the smaller tree under the larger. The larger tree's depth is unchanged, and only nodes in the smaller tree get deeper — but those were in a set at most half the size of the result.

So a node's depth increases only when its set at least doubles.
A set can double only about log n times, so depth stays below log n.
This holds with no path compression at all.

Rank, an upper bound on height, is the common alternative; size is usually preferable because group sizes are often wanted anyway.

Why use both optimisations rather than either alone?

Because they fix different failure modes: union by size stops tall trees from being created, and path compression flattens whatever height does appear. Together the amortised cost is the inverse Ackermann function.

Union by size alone gives a clean O(log n) worst case with no amortisation.
Path compression alone is near-constant amortised and fine in practice.
Both together is the standard implementation and costs two extra lines.

α(n) is below 5 for any input that could physically exist, so treating it as constant in analysis is entirely reasonable.

What is the trap with the size array?

Size is only meaningful at a root. Reading it for a non-root gives a stale value from when that node was last a root, so always call find first and read the size of the returned root.

The bug is silent: the number looks plausible and is simply wrong.
The same applies to any per-set data you attach, such as a minimum, a maximum or a count.
A helper that returns the size of the set containing x, doing the find internally, avoids the mistake entirely.

Storing per-set aggregates at the root is a common and useful extension, which makes the pitfall worth knowing.

Can you undo a union?

Not in the standard structure. Merges are permanent, and edge deletion is not a union-find problem — the structure has discarded which merges came from which edges.

If deletions are known in advance, process the whole sequence backwards, because deletions in reverse are additions.
Rollback is possible by logging each union's changes, but requires dropping path compression, raising cost to O(log n).
If deletions are rare, rebuilding from scratch is often simplest.

The offline reversal trick solves a surprising number of problems that look like they need dynamic connectivity.

How is union-find used in Kruskal's algorithm?

Sort the edges by weight and consider them cheapest first, adding an edge to the tree only if its endpoints are currently in different sets — which is a comparison of two finds.

Endpoints in the same set means the edge would close a cycle, so it is skipped.
Adding the edge is the union, and the process stops once there are n − 1 edges.
The sort dominates, so total cost is O(E log E).

The cycle test being a single comparison is why Kruskal is so simple compared with other minimum spanning tree algorithms.

How would you use it to decide whether water percolates from the top of a grid to the bottom?

Union every pair of adjacent open cells, then add two virtual nodes: one joined to every cell in the top row and one joined to every cell in the bottom row. Percolation is then a single check of whether the two virtual nodes share a root.

Without the virtual nodes you would have to test every top cell against every bottom cell.
The trick generalises: to ask about a whole set of nodes at once, connect them all to one fake node.
It also makes the answer available continuously as cells are opened, rather than only at the end.

This is the standard percolation demonstration, and the virtual-node idea is worth remembering well beyond it.

Union-find or DFS for counting connected components?

DFS if you have the whole graph upfront and just want the count — it is one pass and no extra structure. Union-find if edges arrive over time or queries are interleaved with merges, since it answers each immediately.

The component count with union-find is simply the number of successful unions subtracted from the node count.
DFS also gives you the nodes in each component, which union-find only gives by grouping on roots afterwards.
Union-find handles the streaming case that DFS cannot.

The deciding question is whether all the edges are known before the first query.

How would you extend it to track something per group, such as the largest element?

Store the extra value at the root alongside the size, and combine the two values whenever a union happens — taking the maximum, the sum, or whatever the aggregate is.

Reading it always requires a find first, exactly like size.
The aggregate must be mergeable from two groups without knowing their members, which max, min, sum and count all are.
Something like "the median of the group" is not mergeable this way and needs a different structure.

Asking whether an aggregate can be combined from two partial results is a good general test for whether it fits this pattern.