Number of Connected Components in an Undirected Graph

MediumGraphsDFSBFSGraphUnion Find

Problem

You are given a number of nodes labeled from 0 up to n - 1 and a list of undirected edges connecting pairs of them. Count how many separate connected components the graph splits into, where a node with no edges at all still counts as its own component.

Example. With 5 nodes and edges connecting 0-1, 1-2, and 3-4, the graph has two components: {0, 1, 2} and {3, 4}.

Key idea

Comparing every pair of nodes for reachability would repeat far more work than necessary. Instead, explore the graph once and count how many times a fresh exploration has to begin. Iterate over every node in order; whenever a node has not yet been visited, it must be the first node reached in some component not yet counted, so increment the component count and flood fill outward from it (using depth-first or breadth-first search), marking every node reachable from it as visited so the main iteration skips them later. An equivalent approach uses Union-Find: process every edge by joining its two endpoints into the same set, then count the distinct set representatives left once all edges are processed: that count is the number of components.

Solution

function countComponents(n: number, edges: number[][]): number {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    // undirected: add the edge in both directions
    graph[a].push(b);
    graph[b].push(a);
  }

  const visited = new Array<boolean>(n).fill(false);

  function explore(node: number): void {
    visited[node] = true;
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        explore(neighbor);
      }
    }
  }

  let components = 0;
  for (let node = 0; node < n; node++) {
    if (!visited[node]) {
      components++; // unvisited node starts a new component
      explore(node);
    }
  }

  return components;
}

Complexity

  • Time: O(V + E). Building the adjacency list and visiting every node and edge once, or a near-linear Union-Find pass with path compression.
  • Space: O(V + E). For the adjacency list or Union-Find parent array, plus visited tracking.

Watch out for

  • Nodes that appear in no edge at all still each form their own component; do not only consider nodes mentioned in the edge list.
  • Build an adjacency list up front rather than scanning the full edge list for every node's neighbors, or the traversal degrades badly.
  • With Union-Find, count the distinct roots after all unions finish, not the raw size of the parent array.

Pattern

This is the same flood-fill-and-count technique as Number of Islands, applied to an explicit node-and-edge graph instead of an implicit grid graph. Union-Find is the natural alternative whenever edges arrive one at a time.

Related questions