What you will learn
- What union-find stores and the two operations it supports.
- Path compression and union by size, and why together they’re nearly O(1).
- Three classic problems, plus a randomised check against DFS.
Signals
- “Are these two connected?”, “how many groups/components?”, “merge accounts/friends”.
- Edges arrive one at a time and you need connectivity after each.
- “Which edge creates a cycle?” in an undirected graph.
- Kruskal’s minimum spanning tree.
The data structure
Each element points to a parent; a root points to itself and names its set.
find(x): follow parents to the root.union(a, b): find both roots; if different, attach one root under the other.
Two optimisations make this fast:
- Path compression: after finding the root, point every node on the path directly at it, so future finds are short.
- Union by size (or rank): hang the smaller tree under the larger, so trees stay shallow.
With both, a sequence of m operations takes O(m·α(n)), where α is the inverse Ackermann function, below 5 for any realistic n. Treat it as constant.
Python
"""Union-find (disjoint set union) with path compression and union by size."""
import random
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # path compression: point every node on the path at the root
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected: this edge would close a cycle
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # union by size: hang the smaller tree under the larger
self.size[ra] += self.size[rb]
self.components -= 1
return True
def connected(self, a, b):
return self.find(a) == self.find(b)
def count_components(n, edges):
uf = UnionFind(n)
for a, b in edges:
uf.union(a, b)
return uf.components
def redundant_connection(edges):
uf = UnionFind(len(edges) + 1)
for a, b in edges:
if not uf.union(a, b):
return [a, b]
return None
def accounts_merge(accounts):
uf, owner, email_id = UnionFind(sum(len(a) - 1 for a in accounts)), {}, {}
for name, *emails in accounts:
for e in emails:
if e not in email_id:
email_id[e] = len(email_id)
owner[e] = name
uf.union(email_id[emails[0]], email_id[e])
groups = {}
for e, i in email_id.items():
groups.setdefault(uf.find(i), []).append(e)
return sorted([owner[es[0]], *sorted(es)] for es in groups.values())
def components_by_dfs(n, edges):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen, count = set(), 0
for s in range(n):
if s not in seen:
count += 1
stack = [s]
seen.add(s)
while stack:
for nxt in graph[stack.pop()]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return count
if __name__ == "__main__":
print(count_components(5, [[0, 1], [1, 2], [3, 4]]))
print(redundant_connection([[1, 2], [1, 3], [2, 3]]), redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))
print(accounts_merge([["John", "j@x.com", "john@y.com"], ["John", "john@y.com", "jj@z.com"],
["Mary", "mary@m.com"], ["John", "johnny@n.com"]]))
random.seed(1)
for _ in range(500):
n = random.randint(1, 30)
edges = [[random.randrange(n), random.randrange(n)] for _ in range(random.randint(0, 40))]
assert count_components(n, edges) == components_by_dfs(n, edges)
print("500 random graphs: union-find matches DFS")
Output:
2
[2, 3] [1, 4]
[['John', 'j@x.com', 'jj@z.com', 'john@y.com'], ['John', 'johnny@n.com'], ['Mary', 'mary@m.com']]
500 random graphs: union-find matches DFS
- Count components: start with n components and subtract one per successful union.
- Redundant connection: the first edge whose endpoints are already connected closes a cycle;
unionreturnsFalsefor it. - Accounts merge: union every email in an account with the account’s first email, then group emails by root. Two “John” accounts sharing
john@y.commerge; the third John stays separate because the name alone proves nothing. - The random test compares component counts against a plain DFS on 500 graphs, including self-loops and repeated edges.
Java
public class UnionFind {
private final int[] parent;
private final int[] size;
private int components;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving: skip a level on the way up
x = parent[x];
}
return x;
}
public 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];
components--;
return true;
}
public int components() { return components; }
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
int[][] edges = {{0, 1}, {1, 2}, {3, 4}, {2, 0}};
for (int[] e : edges) {
if (!uf.union(e[0], e[1])) System.out.println("cycle at edge " + e[0] + "-" + e[1]);
}
System.out.println("components: " + uf.components());
}
}
Output:
cycle at edge 2-0
components: 2
The Java version uses path halving (parent[x] = parent[parent[x]] while walking up), a one-pass variant of path compression with the same complexity.
Union-find vs BFS/DFS
| Situation | Better choice |
|---|---|
| Static graph, one-off component count | Either; DFS is simple |
| Edges arrive over time, connectivity queries in between | Union-find |
| Need actual paths or distances | BFS/DFS |
| Kruskal’s MST, cycle detection while adding edges | Union-find |
| Deleting edges | Neither directly (offline tricks needed) |
Practise: union-find problems and the wider graph traversal section.
Key takeaways
- Union-find tracks a partition into sets with
findandunion. - Path compression plus union by size gives effectively O(1) amortised operations.
- A failed union (same root) means the edge closes a cycle.
- Prefer it when edges arrive incrementally and you only need connectivity.
Exercises
- Number of provinces from an adjacency matrix with union-find.
- Kruskal’s minimum spanning tree: sort edges by weight, union if not connected.
- Longest consecutive sequence (LeetCode 128) using union-find over values.
Quiz
- What does
findreturn, and what does it mean if two elements return the same value? - What do path compression and union by size each prevent?
- How does union-find detect a cycle in an undirected graph?
Show answers
- The root representative of the element’s set; the same root means the two elements are in the same set (connected).
- Path compression flattens long paths created earlier; union by size stops tall trees forming in the first place.
- When adding edge (a, b), if
find(a) == find(b)they’re already connected, so the edge closes a cycle.