Overview
Union-Find maintains a collection of disjoint groups. It supports two operations: find(x) returns a representative of x's group, and union(a, b) merges the groups containing a and b. Each group is stored as a tree of parent pointers, and the representative is the root.
Two small optimisations make it astonishingly fast. Path compression flattens the tree every time you call find, and union by size (or rank) always hangs the smaller tree under the larger one. Together they bring the amortised cost to O(α(n)), where α is the inverse Ackermann function — at most 4 for any input that fits in the universe.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| find / union (both optimisations) | O(α(n)) amortised ≈ O(1) |
| Without optimisations | O(n) per operation worst case |
| Kruskal's MST | O(E log E) — dominated by sorting |
Patterns to recognise
Dynamic connectivity
Use it for: Number of provinces, network connected, redundant connection.
Union every edge; query or count components afterwards.
Equivalence grouping
Use it for: Accounts merge, satisfiability of equations, similar strings.
Union things that are "equal", then check or collect groups by root.
Minimum spanning tree
Use it for: Min cost to connect all points.
Sort edges, union greedily, stop after V − 1 edges.
Code template
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
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 connected
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # smaller tree under larger
self.size[ra] += self.size[rb]
self.components -= 1
return True
struct DSU {
vector<int> parent, sz;
int components;
explicit DSU(int n) : parent(n), sz(n, 1), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (sz[ra] < sz[rb]) swap(ra, rb);
parent[rb] = ra;
sz[ra] += sz[rb];
--components;
return true;
}
};
Common mistakes
- Setting parent[a] = b instead of linking the roots corrupts the structure.
- Map non-integer identifiers (emails, strings) to integer ids first, or use a dictionary-based DSU.
- Union-Find answers connectivity in undirected graphs; it cannot handle edge deletions or directed reachability.
Quick check
Three questions on Union-Find. Get all three right to earn +15 XP.
-
What does find(x) return?
Two elements are in the same set exactly when their roots are equal.
-
What does path compression do?
It flattens the tree, so later finds are nearly O(1).
-
While adding edges of an undirected graph, when does Union-Find signal a cycle?
The endpoints were already connected, so the new edge closes a loop.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Number of ProvincesLeetCode Medium +40
- Redundant ConnectionLeetCode Medium +40
- Accounts MergeLeetCode Medium +40
- Number of Operations to Make Network ConnectedLeetCode Medium +40
- Satisfiability of Equality EquationsLeetCode Medium +40
- Most Stones Removed with Same Row or ColumnLeetCode Medium +40
Stuck on Union-Find?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor