medium

Number of Connected Components in an Undirected Graph

Count the number of connected components in an undirected graph.

1. Define the problem

Number of Connected Components in an Undirected Graph

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and edges where edgesi = [ai, bi] indicates an undirected edge between ai and bi. Return the number of connected components in the graph. Union every edge and count how many merges actually combine two different groups — every merge shrinks the group count by one.

Constraints

  • 1 ≤ n ≤ 2000
  • 1 ≤ edges.length ≤ 5000
  • edgesi.length == 2
  • 0 ≤ ai ≤ bi < n
  • ai != bi
  • There are no repeated edges

Example

Inputn = 5, edges = [[0,1],[1,2],[3,4]]
Output2

Explanation Nodes {0, 1, 2} form one component and nodes {3, 4} form another.

2. Visualize the solution

Union every edge, count merges that reduce the group total

Union every edge, count merges that reduce the group total
Statusunion

Union [0, 1]. Component count drops from 5 to 4.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
size[0] = 1, size[1] = 1 → not smaller, so attach root 1 under root 0
parent[1] = 0
size[0] = 1 + 1 = 2
components: 5 → 4

Nodes 0 and 1 merge under root 0.
Step 1 of 3

Steps to visualize

  1. Start with n groups, one per node.
  2. For each edge, union its two endpoints.
  3. Every time a union actually joins two different groups, decrement the running component count.
  4. When every edge is processed, the count is the number of connected components.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union every edge, count merges that reduce the group total
Statusunion

Union [0, 1]. Component count drops from 5 to 4.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
size[0] = 1, size[1] = 1 → not smaller, so attach root 1 under root 0
parent[1] = 0
size[0] = 1 + 1 = 2
components: 5 → 4

Nodes 0 and 1 merge under root 0.
Step 1 of 3
4. Solution

Solution

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

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

  for (const [a, b] of edges) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) continue;

    if (size[rootA] < size[rootB]) {
      parent[rootA] = rootB;
      size[rootB] += size[rootA];
    } else {
      parent[rootB] = rootA;
      size[rootA] += size[rootB];
    }
    components--;
  }

  return components;
}
Time
O(n + e) · α(n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
n = 5, edges = [[0,1],[1,2],[3,4]]2example from the docstring
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]1a single chain connects every node
n = 4, edges = []4no edges at all, every node is its own component
n = 6, edges = [[0,1],[2,3],[4,5]]3three separate pairs of connected nodes
n = 3, edges = [[0,1],[1,0]]2the same connection listed twice in reverse order has no extra effect
n = 1, edges = []1smallest valid input, a single node with no edges

Keep reading