vizlearn
Home / Algorithms

Union-Find (Disjoint Set)

Algorithms & Data StructuresBy Updated

Track which items belong to the same group, and merge groups instantly. Two small optimisations take it from linear to effectively constant time — and Kruskal's MST algorithm depends on it entirely.

Controls

Forest of Sets

step 0
parent[] array

Insight

Each set is a tree; the root is the set's representative. Find walks to the root, Union links one root under another.

groups8
max depth1
last find steps–

Complexity

With both opts O(α(n))
No optimisations O(n)
Space O(n)

Overview

Each element points to a parent. A root points to itself and represents its set. Two elements belong to the same group when their roots are equal. To merge groups, find both roots and attach one root to the other.

Parent trees represent groups

Choose Build a bad chain with the union by rank and path compression options off. A find can then follow a long chain. Turn on union by rank and rebuild: attaching the shallower tree under the deeper one keeps the height logarithmic. Equal-rank roots can be joined and the resulting rank increased by one.

Path compression shortens later searches

During find, path compression makes nodes on the path point directly to the root, so future searches traverse fewer links. Use Find(a) — show path to see the links update. Union(a, b) merges the two groups; Same group? checks whether two elements share a representative.

With both union by rank and path compression, a sequence of operations has amortized O(α(n)) cost per operation, where α is the inverse Ackermann function. It grows so slowly that it is below 5 for any practical input size, but the bound is not exactly constant.

HeuristicEffect
Union by rankKeeps tree height logarithmic without compression
Path compressionFlattens paths during find
BothAmortized inverse-Ackermann cost across operations

Where it is useful

Union-Find fits connectivity problems where groups merge but never split. Kruskal’s minimum spanning tree algorithm uses it to check whether an edge would connect vertices already in the same component. It also supports connected-component tracking in undirected graphs and grouping equivalent identifiers.

What it cannot do

The structure does not efficiently split a group or remove an edge while preserving general dynamic connectivity. If the application needs deletions, use a structure designed for that case or an offline rollback variant. Union-Find also does not answer directed reachability or shortest-path questions.

Common mistakes with Union-Find

  • Unioning elements instead of their roots: attach representatives, not arbitrary nodes.
  • Counting a repeated union as a new merge: if roots match, the number of components does not change.
  • Calling the bound constant: inverse-Ackermann is effectively tiny in practice but remains a function.
  • Using it for deletions: ordinary disjoint-set union only merges components.

Sources and next steps

Run it in Python

The same twelve operations run twice: once on a naive implementation, once with union by rank and path compression, with pointer hops counted. The difference between the two counts is the whole reason the optimisations exist.

union_find.pyPython 3
Output
How the code works
  1. self.parent = {x: x for x in items}Every element starts as its own root, so there are n groups of one. “Which group is x in?” is always answered by walking to the root, and the root's identity is the group's name.
  2. self.parent[ra] = rb   # naiveAttaching without looking at the shapes is what builds a chain. Merge in a line, as the sample does, and find degrades to O(n) — a linked list wearing a tree's name.
  3. if self.rank[ra] < self.rank[rb]: ra, rb = rb, raUnion by rank: hang the shorter tree under the taller one so the depth does not grow. Rank is an upper bound on height, not the exact height, which is why compression can leave it stale without breaking anything.
  4. while self.parent[x] != root: self.parent[x], x = root, self.parent[x]Path compression. Every node touched on the way up is re-pointed straight at the root, so the next query on any of them is one hop. The work of the walk is what pays for the next walk.
  5. dsu.hopsTogether these give near-constant amortised time — O(α(n)), where α is the inverse Ackermann function and is below 5 for any n that fits in a computer. The hop counts printed here are that theory, measured.
Change one thing
  • Raise items to range(1000) with the same chain of merges. The naive count explodes quadratically; the optimised one barely moves.
  • Delete only the compression loop, keeping rank. Most of the win survives — either optimisation alone is already good.
  • Add a count field decremented on each successful union. That is how union-find answers “how many connected components?” in O(1).
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: press Build a bad chain. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. What does path compression do?
  2. Union by rank exists to prevent:
  3. With both optimisations, the amortised cost per operation is:





 Cheat sheet
Union-Find (Disjoint Set)
Merge and query disjoint sets in near-constant time with union by rank and path compression — the engine inside Kruskal's MST.
ALGORITHMS · vizlearn.in/dsa/union_find.html
More in Algorithms
AlgorithmsGraph RepresentationsAlgorithmsBreadth First SearchAlgorithmsDepth First SearchAlgorithmsCycle Detection
Further reading
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact