Number of Connected Components in an Undirected Graph
Medium
Problem
You are given n nodes labeled 0 to n - 1 and a list of undirected edges. Return how many connected components the graph has. A node with no edges is its own component.
Examples
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Example 3:
Input: n = 4, edges = []
Output: 4
Example 4:
Input: n = 6, edges = [[0,1],[2,3],[4,5]]
Output: 3
Constraints
1 <= n <= 2000
0 <= edges.length <= 5000
No self-loops or duplicate edges.
Prerequisites
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. Union-Find, Counting Merges Optimal
Intuition
Start by assuming nothing is connected: n nodes, n components. Every edge that joins two DIFFERENT groups reduces the count by one; an edge inside a group changes nothing. The count falls out of the merges without any traversal at all.
Algorithm
1. Every node is its own parent; components equals n. 2. For each edge, find both roots. 3. Different roots: union them and decrement the count. 4. The remaining count is the answer.
Time & Space
Time near O(edges) with path compression. Space O(n). A DFS counting fresh starts is the same answer by another road.