Union-find — also called disjoint set union, or DSU — is a data structure built to answer one question fast: are these two elements in the same group. It supports exactly two operations, find and union, and the design effort behind it goes into making both run in close to constant time, even across millions of merges.
What changed in 2026
- It stayed exactly the same, and that is the point. Union-find with path compression and union by rank has been near-optimal since the 1980s; nothing about the core algorithm needed to change. What shifted is where it shows up — more graph libraries expose it as a first-class utility instead of something you hand-roll.
- It became a common building block in dedupe and entity-resolution pipelines. Merging records that reference the same underlying entity across noisy datasets is a union-find problem in disguise, and more data tooling names it as such now.
- Interview and systems-design emphasis picked back up. As graph and dependency reasoning became more visible in day-to-day engineering work, union-find re-entered technical interviews alongside topological sort as a "can you reason about connectivity" check.
The two operations
- find(x) — returns a representative (or "root") for the group x belongs to. Two elements are in the same group exactly when find returns the same root for both.
- union(x, y) — merges the groups containing x and y into one group.
That is the entire interface. No iteration over members, no ordering, no removal. If your problem needs more than "same group or not," union-find alone is not enough.
Why the naive version is not good enough
The simplest implementation stores a parent pointer per element and walks up to the root on every find. Left alone, repeated unions can build a long chain, turning what should be a fast lookup into an O(n) walk. Two small additions fix this completely:
- Path compression — while walking up during find, point every node on the path directly at the root. Future finds on those nodes become instant.
- Union by rank or size — when merging two groups, always attach the smaller (or shallower) tree under the root of the larger one, instead of picking arbitrarily.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
Naive vs optimized performance
| Version |
find / union cost |
Notes |
| Parent pointers only |
Up to O(n) per operation |
Can degrade to a linked list |
| + Union by rank only |
O(log n) per operation |
Keeps trees shallow |
| + Path compression only |
Close to O(log n) amortized |
Flattens paths over time |
| Both combined |
Amortized inverse-Ackermann — effectively constant |
Standard production implementation |
The combined version is fast enough that, for any input size that fits in memory, you can treat each operation as roughly constant time in practice.
Where union-find actually gets used
- Kruskal minimum spanning tree. Sort edges by weight, and add each edge only if its two endpoints are not already unioned — this is exactly what prevents a cycle from forming.
- Cycle detection in undirected graphs. If union(x, y) is called and find(x) already equals find(y), that edge would create a cycle.
- Connected components. Union every pair of directly connected nodes, then group elements by their final root.
- Image processing. Labeling connected regions of pixels is a grid version of the same connectivity problem.
Common mistakes
Forgetting path compression, union by rank, or both. Either alone is fine; skipping both causes the classic worst-case slowdown people warn about.
Expecting union-find to support "un-union." It is a one-directional merge structure. If you need to split groups back apart, you need a different structure or need to rebuild.
Trying to list all members of a group cheaply. Union-find does not track membership lists by default; you would need to maintain that separately if your problem requires it.
FAQ
Is union-find the same as a graph?
No. It represents a partition into disjoint groups, not edges and paths between individual nodes, though it is commonly used alongside graph algorithms.
What does the inverse-Ackermann time complexity actually mean?
It grows so slowly that for any input size you could realistically store in memory, it is indistinguishable from a small constant. It is not literally O(1), but it behaves like it in practice.
Can union-find detect cycles in a directed graph?
Not directly — it is built for undirected connectivity. Directed-graph cycle detection needs a different approach, such as the DFS coloring method used to validate a directed acyclic graph.
Do I need union by rank if I already have path compression?
Both together give the best guaranteed bound. Path compression alone is very fast in practice, but combining both is the standard, safest choice.
Where to go next