Number of Connected Components in an Undirected Graph

Problem

Network monitoring tools need to detect isolated clusters of machines after link failures. Given n nodes labeled 0 to n-1 and a list of undirected edges, return the number of connected components in the graph.

n=5, edges=[[0,1],[1,2],[3,4]]     → 2  (component {0,1,2} and {3,4})
n=5, edges=[[0,1],[1,2],[2,3],[3,4]] → 1  (all connected)
n=4, edges=[]                       → 4  (all isolated)

Solution

Approach: DFS from every unvisited node, counting one component per launch.

First build an adjacency list from the edge list. Because the graph is undirected, each edge (u, v) is added in both directions - v into adjacency[u] and u into adjacency[v] - otherwise DFS could only traverse the edge one way and would miss nodes. Then walk nodes 0 through n-1. The key idea: a single DFS launched from any node visits exactly the nodes in that node's connected component and marks them all in the shared visited set. So whenever the outer loop hits a node that is still unvisited, that node must belong to a component not yet seen - launch DFS to claim the whole component and increment the counter once. Every node the DFS reaches is added to visited, so later outer-loop iterations skip them, and each component contributes exactly one increment regardless of size. Trace n=5, edges=[[0,1],[1,2],[3,4]]: node 0 is unvisited, its DFS sweeps , counter becomes 1; nodes 1 and 2 are now skipped; node 3 is unvisited, its DFS sweeps , counter becomes 2; the answer is 2.

Edge cases: No edges means every node is its own component, so the loop increments n times. A fully connected graph yields 1 - the first DFS claims everything. Isolated nodes are counted naturally since each is unvisited when the loop reaches it.

Complexity: O(V + E) time, O(V + E) space - each node and edge is touched once; the adjacency list is O(V + E), the visited set and recursion stack O(V).