Number of Connected Components

Difficulty: Medium

Problem

You are given n nodes labeled 0 to n−1 and a list of undirected edges. Return the number of connected components — the separate 'pieces' the graph falls into. You counted islands on a grid; this is the same question on a real node-and-edge graph.

Example

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: Nodes {0, 1, 2} form one piece (chained by two edges) and {3, 4} form another. Two pieces → 2.

Brute-force approach

No brute-force phase for graph problems — scan-and-flood IS the approach.

Optimal approach

Key insight: The scan discovers each piece exactly once; the flood erases the rest of the piece from future discovery. Islands, without the grid.

Build the adjacency list, then scan every node: each unvisited one starts a new component (count it) and a BFS claims all of its members.

Steps

1. Build the adjacency list (both directions per edge)
2. For each node 0..n−1: if visited, skip
3. Otherwise count += 1 and BFS from it, marking every reachable node
4. Return the count

Time complexity: O(V + E) · Space complexity: O(V + E)