Union-Find (Disjoint Set) Explained

Union-find, also called a disjoint-set data structure, keeps track of a collection of elements partitioned into non-overlapping groups and answers one question extremely fast: are these two elements in the same group? It supports two operations — union(a, b), which merges the groups containing a and b, and find(a), which returns an identifier for the group a currently belongs to. Two elements are connected exactly when find returns the same identifier for both.

The core idea: trees as groups

Each group is represented internally as a tree, where every element points to a parent, and the root of the tree serves as the group’s identifier. Initially, every element is its own group — its own single-node tree, pointing to itself:

parent[a] = a
parent[b] = b
parent[c] = c

union(a, b) merges the two trees by making one root point at the other:

union(a, b): parent[find(a)] = find(b)

find(x) walks up parent pointers until it reaches an element that points to itself — the root:

find(x):
  while parent[x] != x:
    x = parent[x]
  return x

Two elements are in the same set if find walks up to the same root for both. This is the entire idea; the sophistication is entirely in how to keep those trees shallow so find stays fast even after many unions.

Why naive union-find gets slow

If union always attaches one root directly under the other without any care, repeated unions can produce a long chain — effectively a linked list — where find has to walk through every previously merged element to reach the root. That degrades to linear time per find, which defeats the purpose of the structure. Two optimizations fix this, and together they’re what make union-find one of the fastest data structures in practice for its specific job.

Optimization 1: union by rank or size

Instead of arbitrarily attaching one root under the other, always attach the smaller (or shorter) tree under the root of the larger one. This keeps the resulting tree from growing taller than necessary — attaching a small tree under a big one adds at most one to the depth of the small tree’s elements, while attaching a big tree under a small one could add depth to a much larger number of elements. Tracking each tree’s size (element count) or rank (an upper bound on height) and always merging the smaller into the larger keeps tree height logarithmic in the number of elements.

Optimization 2: path compression

Every time find(x) walks up to the root, it can rewrite every node it passed through to point directly at that root, flattening the path for next time:

find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])  # point directly at the root
  return parent[x]

The next find on any of those nodes — or any node that shares an ancestor with them — is now a single hop. Path compression alone dramatically shortens future lookups; combined with union by rank, the amortized cost of each operation becomes effectively constant — technically bounded by the inverse Ackermann function, a quantity that grows so slowly it’s smaller than 5 for any input size that could exist in practice, which is why it’s treated as constant time in real-world analysis. See Big O notation for how amortized bounds like this are expressed and compared against other structures.

What it’s used for

For elements that aren’t already small integers — strings, coordinates, arbitrary objects — the parent pointers are usually backed by a hash table mapping each element to its parent, rather than a plain array, but the union and find logic is otherwise unchanged.

• Kruskal’s minimum spanning tree algorithm — process edges from smallest to largest weight, and use union-find to reject any edge that would connect two nodes already in the same set (which would create a cycle rather than extend the tree).
• Cycle detection in undirected graphs — attempting to union two nodes that are already in the same set signals a cycle, which is a cheaper check than a full traversal for this specific question. This complements the traversal-based approach in BFS and DFS, which can also detect cycles but at higher per-check cost when you only need a yes/no answer repeatedly.
• Connected components — after processing every edge in a graph with union, all nodes sharing a root are in the same connected component, answered without a separate traversal per component.
• Dynamic connectivity queries — answering “are these two nodes connected?” repeatedly as edges are added over time, which is exactly the scenario union-find is built for, since it doesn’t need to be rebuilt from scratch after each addition the way a fresh traversal would.

Union-find vs a graph traversal

A BFS or DFS traversal can also determine whether two nodes are connected, but it has to walk the graph from scratch (or maintain a separately-updated visited structure) for every query, and it doesn’t handle incremental edge additions well without recomputation. Union-find is purpose-built for exactly this incremental case: add connections over time, and cheaply check group membership as you go, without ever needing to re-traverse anything. The tradeoff is that union-find only answers “are these connected,” not “what’s the shortest path between them” — for that, you still need a traversal or a shortest-path algorithm.

The takeaway

Union-find represents groups as trees, using union to merge two groups and find to identify which group an element belongs to by walking to the tree’s root. On its own this can degrade to linear-time lookups, but union by rank (attach the smaller tree under the larger) and path compression (flatten paths during find) together bring both operations to near-constant amortized time. It’s the standard tool whenever a problem needs cheap, incremental “are these two things connected” queries — cycle detection, connected components, and Kruskal’s algorithm all lean on it directly.