275. Number of Connected Components in an Undirected Graph
An undirected graph has n nodes labeled 0 through n - 1. The array edges lists its connections: each entry [u, v] means nodes u and v are joined by an edge.
A connected component is a group of nodes where every node can reach every other by walking along edges, and no node in the group connects to anything outside it. A node with no edges is a component all by itself.
Your function receives the integer n and the array edges, and returns a single integer: how many connected components the graph contains.
Example 1:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: Nodes {0, 1, 2} form one component via the edges 0—1 and 1—2; nodes {3, 4} form a second.
Example 2:
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1
Explanation: The four edges chain all five nodes together into a single component.
Constraints:
- 1 ≤ n ≤ 2000
- 0 ≤ m ≤ 5000
- 0 ≤ u, v < n and u ≠ v
- No edge appears more than once.
Hints:
Every node starts alone in its own component, so the count begins at n. What happens to that count each time an edge joins two nodes that were, until now, in different components?
Flood fill works: pick any unvisited node, BFS/DFS to mark everything reachable from it, and count how many times you had to start a fresh flood.
Union-Find: give every node a parent pointer, let find(x) walk to the root, and union two roots per edge. Start the count at n and subtract one per union that actually merges two different roots.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Expected output: 2