Number of Connected Components in an Undirected Graph

A graph has n nodes labelled 0 to n - 1. You are given a list edges where each edges[i] = [a, b] is an undirected edge between nodes a and b.

A connected component is a maximal group of nodes in which every node can reach every other node by following edges. Return the number of connected components. A node with no edges forms a component on its own.

Example 1

Example 2

Example 3

Constraints

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2, 0 <= a, b < n, a != b
• No edge appears more than once.

Pattern Path · Graphs: Ordering & Union-Find · problem 144 of 169

Start simple

For each node, run a fresh search to find its component and compare against all others: O(n · (n + e)) time.

The key idea

Begin with n components, one per node, and process the edges one at a time. Each edge either joins two different components (the count drops by one) or lands inside a component that is already connected (nothing changes). The final count is the answer.

A union-find structure answers "which group is this node in?" quickly. Each node points to a parent, and following parents leads to a group's representative, its root. To process an edge, find both roots: equal roots mean the edge is redundant; otherwise, attach the smaller tree under the larger one.

Two tricks keep the trees almost flat: union by size (attach the smaller group under the larger) and path compression (point nodes closer to the root while searching). Together they make each operation run in nearly constant amortised time, the inverse Ackermann function α(n).

A DFS or BFS that starts a new search from each unvisited node is equally valid, at O(n + e). Union-find shines when edges arrive one by one and you need the count after each.

Complexity

• Time: O(n + e · α(n))
• Space: O(n)

Python

class Solution:
    def countComponents(self, n, edges):
        parent = list(range(n))
        size = [1] * n

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path halving
                x = parent[x]
            return x

        components = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                continue  # already connected
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra  # attach smaller group under larger
            size[ra] += size[rb]
            components -= 1
        return components

JavaScript

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

  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };

  let components = n;
  for (const [a, b] of edges) {
    let ra = find(a), rb = find(b);
    if (ra === rb) continue; // already connected
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra; // attach smaller group under larger
    size[ra] += size[rb];
    components--;
  }
  return components;
};

What the interviewer is checking

The interviewer is checking that you recognise a connectivity question and can implement union-find correctly (or a clean graph traversal), including isolated nodes.

Mistakes to avoid

• Forgetting isolated nodes that appear in no edge; they are still components.
• Treating the graph as directed, adding only a → b to the adjacency list.
• A recursive DFS on a long path can exceed the recursion limit; use an explicit stack or union-find.
• Union-find without path compression or union by size, which degrades to O(n) per lookup on chains.

Follow-ups to expect

• Edges arrive in a stream: report the count after each. (Union-find, decrement on merge.)
• Is the graph a valid tree? (One component and exactly n - 1 edges.)
• What if edges can also be deleted? (Offline reversal or dynamic connectivity.)

In real software

Grouping accounts that share an email or device, finding islands of connected pixels in image segmentation, and detecting network partitions are all component counting, often done with union-find.

Practice next