Why Union-Find exists
Graphs have connected components. Given a graph with n nodes and a stream of edges being added, how do you efficiently answer "are nodes A and B in the same component?" after each edge is added? BFS/DFS works but costs O(n + e) per query on a graph with n nodes and e edges — too slow when you have thousands of queries. Union-Find answers each query in O(α(n)) ≈ O(1) amortized. This makes it the right tool for: online connectivity queries, Kruskal's MST algorithm, cycle detection in undirected graphs, and problems where elements need to be grouped dynamically.
Full implementation with path compression + union by rank
```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) # each node is its own parent self.rank = [0] * n # rank (approximate depth) of each tree self.components = n # number of disjoint sets def find(self, x): # Path compression: make every node point directly to root if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return False # already in the same set # Union by rank: attach smaller tree under larger tree 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 self.components -= 1 return True # successfully merged def connected(self, x, y): return self.find(x) == self.find(y) ``` Time: O(α(n)) per operation. Space: O(n). The `rank` prevents tall trees from forming. Without it, repeated unions could create a chain of length n, making find() O(n). With union by rank + path compression, the amortized cost per operation is O(α(n)) — the inverse Ackermann function, which is ≤ 4 for any n we'd ever see in practice.
Template — Number of Connected Components
```python def countComponents(n, edges): uf = UnionFind(n) for u, v in edges: uf.union(u, v) return uf.components ``` That's it. Initialize n nodes, union all edges, count remaining components. This pattern handles LC 323 (Number of Connected Components), LC 547 (Number of Provinces — same problem with an adjacency matrix), and LC 261 (Graph Valid Tree — a tree has n nodes, n-1 edges, and is fully connected).
Template — Cycle detection in undirected graph
```python def hasCycle(n, edges): uf = UnionFind(n) for u, v in edges: if not uf.union(u, v): return True # union returns False if already connected = cycle return False ``` If union(u, v) returns False, it means u and v were already in the same component — adding this edge creates a cycle. This is the foundation of Kruskal's MST algorithm (add edges in sorted weight order, skip if union returns False). LC 684 (Redundant Connection): return the first edge that causes union() to return False.
Template — Accounts Merge (string nodes)
When node labels are strings (emails, names) instead of integers, use a dictionary to map strings to integer IDs: ```python def accountsMerge(accounts): uf = UnionFind(len(accounts) * 10) # overestimate size email_to_id = {} # email → assigned integer id email_to_name = {} uid = 0 for account in accounts: name = account[0] for email in account[1:]: if email not in email_to_id: email_to_id[email] = uid uid += 1 email_to_name[email] = name uf.union(email_to_id[account[1]], email_to_id[email]) # union all to first from collections import defaultdict root_to_emails = defaultdict(list) for email, eid in email_to_id.items(): root_to_emails[uf.find(eid)].append(email) return [[email_to_name[emails[0]]] + sorted(emails) for emails in root_to_emails.values()] ``` This pattern (string → id → Union-Find) also applies to LC 990 (Equality Equations), LC 1202 (Smallest String With Swaps).