Union-Find
On this page
Connections keep arriving: "user 3 and user 7 are the same person", "server A can now reach server B", "these two accounts share an email". After each one you need to answer "are X and Y in the same group?" or "how many groups are there now?". Re-running a DFS over the whole graph after every new edge is far too slow. Union-find keeps the groups up to date as edges arrive, at almost O(1) per operation.
This page covers both the data structure and the pattern: the Union-Find problems in the Problems section build on it directly.
How it works
Every group is a tree with a representative

Union-find (also called a disjoint set union, or DSU) keeps a parent array. At the start every element is its own parent: n groups of one. Two operations:
- find(x): follow parent pointers until you reach an element that is its own parent. That root is the group's representative.
- union(a, b): find both roots; if they differ, make one root point to the other. The two groups are now one.
"Are a and b connected?" is just find(a) == find(b).
Union by size

If you always attach the smaller tree under the larger, no element's depth can grow beyond about log₂ n, because every time an element gets one level deeper, its group at least doubles in size. Track size[root] and compare.
Path compression

While find walks to the root, re-point the nodes it passes at (or closer to) the root. A simple version is path halving: parent[x] = parent[parent[x]] at each step. With both tricks the cost per operation is "inverse Ackermann", which is at most 4 or 5 for any input you'll ever see. In interviews, say "nearly O(1), amortized".
Operations and costs
| Operation | No tricks | Union by size + path compression |
|---|---|---|
| find | O(n) worst case | nearly O(1) amortized |
| union | O(n) worst case | nearly O(1) amortized |
| connected(a, b) | O(n) | nearly O(1) |
| Count groups | O(1) if you keep a counter | O(1) |
| Memory | O(n) | O(n) |
When to reach for it
- Edges arrive over time and you need connectivity after each one (dynamic connectivity, Number of Islands II).
- Count groups after a set of merges (connected components, friend circles, provinces).
- Detect a cycle in an undirected graph: if both ends of a new edge already have the same root, that edge closes a cycle (Redundant Connection, Graph Valid Tree).
- Group items by shared attributes: union every pair that shares something, then collect each root's members (Accounts Merge).
- Kruskal's minimum spanning tree: sort edges by weight and add each one unless it would close a cycle.
Union-find or DFS? If the graph is fixed and you need components once, DFS is just as good. Union-find wins when edges keep arriving, or when you only need "same group?" answers and not paths. It can't remove edges or tell you the path between two nodes.
Example
A reusable class with union by size and path halving:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.groups = 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: this edge closes a cycle
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach the smaller tree under the larger
self.size[ra] += self.size[rb]
self.groups -= 1
return True
class UnionFind {
private final int[] parent, size;
int groups;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
groups = n;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
groups--;
return true;
}
}
class UnionFind {
vector<int> parent, sz;
public:
int groups;
UnionFind(int n) : parent(n), sz(n, 1), groups(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool unite(int a, int b) { // "union" is a C++ keyword
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];
groups--;
return true;
}
};
type UnionFind struct {
parent, size []int
groups int
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), size: make([]int, n), groups: n}
for i := range uf.parent {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
func (uf *UnionFind) Find(x int) int {
for uf.parent[x] != x {
uf.parent[x] = uf.parent[uf.parent[x]]
x = uf.parent[x]
}
return x
}
func (uf *UnionFind) Union(a, b int) bool {
ra, rb := uf.Find(a), uf.Find(b)
if ra == rb {
return false
}
if uf.size[ra] < uf.size[rb] {
ra, rb = rb, ra
}
uf.parent[rb] = ra
uf.size[ra] += uf.size[rb]
uf.groups--
return true
}
Time: nearly O(1) per operation, so O(n + m) for n elements and m unions in practice. Space: O(n).
With 6 elements and unions (1,0), (2,0), (3,2), (5,4) there are 2 groups and find(3) != find(5). union(3, 5) merges them into one group; a later union(1, 4) returns false because 1 and 4 are already connected, which is exactly the "this edge closes a cycle" signal.
Common mistakes
- Comparing elements instead of roots.
parent[a] == parent[b]is wrong; comparefind(a) == find(b). - Linking the elements, not the roots.
parent[a] = bcan break the structure; always linkfind(a)'s root tofind(b)'s root. - Updating size on the wrong root. Add the smaller tree's size to the root that stays a root.
- Forgetting the group counter when the problem asks "how many groups now?", then recounting in O(n) each time.
- Non-integer items. Map strings (like emails) to integer ids with a hash map first, or use a dictionary-based parent map.
- Expecting deletions or paths. Union-find can't split groups or return the path between two nodes.
Say this in the interview
- "Edges arrive one at a time and I only need 'are these connected?', so union-find fits: nearly O(1) per operation with union by size and path compression."
- "If union returns false, both ends were already in the same group, so this edge would close a cycle."
- "I'll keep a group counter that drops by one on every successful union, so the number of components is always O(1) to read."
Used in
- Problems (Union-Find): Number of Connected Components in an Undirected Graph, Graph Valid Tree, Redundant Connection, Accounts Merge, Number of Islands II
- Patterns: Graph BFS and DFS (the alternative for fixed graphs)
- Data structures: Graphs, Arrays and Strings (the parent array)