Number of Connected Components in an Undirected Graph

Examples

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2

Nodes 0, 1, 2 are all connected to each other; nodes 3, 4 form a separate connected pair.

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1

The edges form one continuous chain touching every node.

Input: n = 4, edges = []
Output: 4

With no edges at all, every node is its own isolated component.

Constraints

• 1 <= n <= 2000

• 0 <= edges.length <= n × (n - 1) / 2

• There are no self-loops or duplicate edges.

Approach

A connected component is just "everything reachable from one starting node, using the given edges." So one natural approach is: build an adjacency list, then scan through the nodes; every time you hit a node you haven't visited yet, that's a new component - run DFS or BFS from it to mark every node in that component as visited, and increase your count by one.

A cleaner and more scalable approach uses Union-Find: start with every node in its own separate group, then merge the two endpoints of each edge into the same group. Whatever nodes remain unmerged relative to each other are in separate components, so counting the number of distinct group roots left at the end gives the answer directly - without ever building an explicit adjacency list or doing a traversal.

Solutions

DFS Traversal

Build an adjacency list from the edges. Scan every node; whenever an unvisited node is found, that's a new component - run DFS from it to mark its entire component as visited, then move on.

function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const visited = new Array(n).fill(false);
  let count = 0;

  function dfs(node) {
    visited[node] = true;
    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) dfs(neighbor);
    }
  }

  for (let node = 0; node < n; node++) {
    if (!visited[node]) {
      count++;
      dfs(node);
    }
  }

  return count;
}

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

Optimal - Union-Find

Start with n separate groups (one per node). Union the two endpoints of every edge. At the end, count how many nodes are still their own group's root - that count is the number of connected components.

function countComponents(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);
  let components = n;

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return;

    if (rank[rootA] < rank[rootB]) {
      parent[rootA] = rootB;
    } else if (rank[rootA] > rank[rootB]) {
      parent[rootB] = rootA;
    } else {
      parent[rootB] = rootA;
      rank[rootA]++;
    }
    components--; // merging two groups always reduces the total by one
  }

  for (const [a, b] of edges) {
    union(a, b);
  }

  return components;
}

Time: O((V + E) × α(V)) - nearly O(V + E) · Space: O(V)