Learning Outcome
After this lesson, you should be able to use parent and size arrays to merge graph components efficiently.
Problem Statement
Given n nodes and undirected edges, return the number of connected components using Union Find.
| Input | Output | Why |
|---|---|---|
n = 5, edges = [[0,1],[1,2],[3,4]] | 2 | Unioning the edges creates groups {0,1,2} and {3,4}. |
Brute Force Approach
After every edge, run DFS again to recompute groups. This repeats traversal work after each merge.
Optimized Approach
Initialize each node as its own parent. Union endpoints of every edge and decrement the component count only when two different roots merge.
Exact Pseudocode
parent[i] = i
size[i] = 1
components = n
for edge (a, b):
if union(a, b) merges two roots:
components -= 1
return components
find(x):
compress parent pointers until root is foundReference Code
class Solution:
def countComponents(self, n, edges):
parent = list(range(n))
size = [1] * n
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return False
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
return True
components = n
for a, b in edges:
if union(a, b):
components -= 1
return componentsSample Dry Run
| Step | State | Result |
|---|---|---|
| Start | Every node is its own parent | components = 5 |
| Union 0 and 1 | Different roots merge | components = 4 |
| Union 1 and 2 | 2 joins root of 0,1 | components = 3 |
| Union 3 and 4 | Different roots merge | components = 2 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O((n + e) alpha(n)) | Path compression and union by size make each operation almost constant. |
| Space | O(n) | Parent and size arrays store one entry per node. |
Edge Cases
- Repeated edges should not reduce the count twice.
- Self-loops should not reduce the count.
- With no edges, every node is a component.
Interview Checklist
- Only decrement count when roots differ.
- Compress paths in find.
- Attach smaller set under larger set.
FAQs
What does alpha(n) mean?
It is the inverse Ackermann factor, which is effectively constant for interview-sized inputs.
When is Union Find better than DFS?
It is especially useful when connectivity is built through many merge operations.
What is the core pattern?
Disjoint set union.