Number of Connected Components in an Undirected Graph medium
Description
You have an undirected graph with n nodes labeled 0 through n - 1 and an array edges. Return the number of connected components — the count of maximal node groups that are mutually reachable.
Examples
> Case 1:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2 # {0, 1, 2} and {3, 4}
> Case 2:
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1 # everything reachable from anythingConstraints
1 <= n <= 20000 <= edges.length <= n * (n - 1) / 2
The DFS sweep — count traversals
The idea is mechanical: walk every unvisited node, and each time you start a new walk, increment a counter. The number of walks equals the number of components.
for each node in 0..n-1:
if not visited:
components += 1
DFS(node) # marks the whole component visitedEach DFS visits every node in its component exactly once. Across the whole loop, every node is touched once. Each edge is examined twice (once from each endpoint). Total work: O(V + E).
Try it yourself
Approach 1: DFS
Approach 2: Union-Find — the cleanest
Each edge tells us “these two nodes belong in the same component.” Start with each node as its own component (n total) and merge whenever an edge says two are connected. Decrement the counter on every successful merge. The remaining count is the answer.
Union-Find shines here because we never need to traverse — we only need to know “which group is each node in?” The graph might as well be edge-list only; we never build an adjacency list. Cleaner code, less memory, same O(V + E α(V)) time.
The pattern: counting “things you start”
This problem teaches a sub-pattern that shows up everywhere:
Whatever you’re counting (components, islands, distinct groups, isolated chains) usually equals the number of times you “kick off” a new traversal from an unvisited start.
Same trick is the entire solution to Number of Islands (Day 10), Friend Circles, Provinces, and any problem of the form “how many distinct groups are there?”
Analysis
| Approach | Time | Space |
|---|---|---|
| DFS sweep | O(V + E) | O(V + E) |
| Union-Find | O(E · α(V)) | O(V) |
Both are essentially linear. Pick whichever feels more natural — both are correct interview answers.