Number of Connected Components in an Undirected Graph (LC 323)

Count the connected components of an undirected graph given n nodes and an edge list. Solve LeetCode 323 with BFS over an adjacency list or with Union-Find, both in near-linear O(n + e) time.

Language Selection

Choose your preferred programming language

Showing: Python

Number of Connected Components in an Undirected Graph

Problem Statement

You are given n nodes labeled 0 to n - 1 and a list edges, where edges[i] = [a, b] is an undirected edge between nodes a and b. Return the number of connected components in the graph.

A connected component is a maximal group of nodes in which every node can reach every other node through edges. A node with no edges forms a component by itself.

Examples

Example 1:

Input: n = 6, edges = [[0,1],[1,2],[3,4]]
Output: 3
Explanation: The components are {0,1,2}, {3,4} and {5}.
Node 5 has no edges, so it is a component on its own.

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: 1
Explanation: All four nodes sit on one cycle, so there is a single component.
The extra edge that closes the cycle does not change the count.

Example 3:

Input: n = 3, edges = []
Output: 3
Explanation: With no edges, every node is its own component.

Constraints

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

Approach 1: BFS over an Adjacency List

Algorithm

Each time you find a node that no earlier search has reached, it belongs to a brand-new component. Explore that whole component with BFS so none of its nodes are counted again.

  1. Build an adjacency list from the edges.
  2. Keep a seen array. Set components = 0.
  3. For each node i from 0 to n - 1: if i is unseen, increment components and BFS from i, marking every reachable node as seen.
  4. Return components.

Implementation

Python:

from collections import deque
from typing import List


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        seen = [False] * n
        components = 0
        for start in range(n):
            if seen[start]:
                continue
            components += 1            # first node of a new component
            seen[start] = True
            queue = deque([start])
            while queue:               # flood the whole component
                node = queue.popleft()
                for nxt in graph[node]:
                    if not seen[nxt]:
                        seen[nxt] = True
                        queue.append(nxt)
        return components

Java:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        boolean[] seen = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        int components = 0;
        for (int start = 0; start < n; start++) {
            if (seen[start]) continue;
            components++;                  // first node of a new component
            seen[start] = true;
            queue.add(start);
            while (!queue.isEmpty()) {     // flood the whole component
                int node = queue.poll();
                for (int next : graph.get(node)) {
                    if (!seen[next]) {
                        seen[next] = true;
                        queue.add(next);
                    }
                }
            }
        }
        return components;
    }
}

Go:

func countComponents(n int, edges [][]int) int {
    graph := make([][]int, n)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
        graph[e[1]] = append(graph[e[1]], e[0])
    }

    seen := make([]bool, n)
    components := 0
    for start := 0; start < n; start++ {
        if seen[start] {
            continue
        }
        components++ // first node of a new component
        seen[start] = true
        queue := []int{start}
        for head := 0; head < len(queue); head++ { // flood the component
            for _, next := range graph[queue[head]] {
                if !seen[next] {
                    seen[next] = true
                    queue = append(queue, next)
                }
            }
        }
    }
    return components
}

JavaScript:

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function (n, edges) {
    const graph = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const seen = new Array(n).fill(false);
    let components = 0;
    for (let start = 0; start < n; start++) {
        if (seen[start]) continue;
        components++;                   // first node of a new component
        seen[start] = true;
        const queue = [start];
        for (let head = 0; head < queue.length; head++) { // flood the component
            for (const next of graph[queue[head]]) {
                if (!seen[next]) {
                    seen[next] = true;
                    queue.push(next);
                }
            }
        }
    }
    return components;
};

C#:

using System.Collections.Generic;

public class Solution {
    public int CountComponents(int n, int[][] edges) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        foreach (var e in edges) {
            graph[e[0]].Add(e[1]);
            graph[e[1]].Add(e[0]);
        }

        var seen = new bool[n];
        var queue = new Queue<int>();
        int components = 0;
        for (int start = 0; start < n; start++) {
            if (seen[start]) continue;
            components++;                  // first node of a new component
            seen[start] = true;
            queue.Enqueue(start);
            while (queue.Count > 0) {      // flood the whole component
                int node = queue.Dequeue();
                foreach (int next in graph[node]) {
                    if (!seen[next]) {
                        seen[next] = true;
                        queue.Enqueue(next);
                    }
                }
            }
        }
        return components;
    }
}

C++:

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (const auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        vector<bool> seen(n, false);
        int components = 0;
        for (int start = 0; start < n; start++) {
            if (seen[start]) continue;
            components++;                  // first node of a new component
            seen[start] = true;
            queue<int> q;
            q.push(start);
            while (!q.empty()) {           // flood the whole component
                int node = q.front();
                q.pop();
                for (int next : graph[node]) {
                    if (!seen[next]) {
                        seen[next] = true;
                        q.push(next);
                    }
                }
            }
        }
        return components;
    }
};

Complexity Analysis

  • Time: O(n + e). Building the adjacency list is O(n + e), and BFS visits each node once and each edge twice (once from each end).
  • Space: O(n + e) for the adjacency list, plus O(n) for seen and the queue.

Approach 2: Union-Find (Optimal)

Algorithm

Start with n separate components, one per node. Every edge that joins two nodes from different components merges them, which lowers the count by one. An edge between nodes already in the same component (one that closes a cycle) changes nothing. So the answer is n minus the number of successful merges.

  1. Set parent[i] = i, size[i] = 1, and components = n.
  2. For each edge (a, b), find the roots of a and b.
  3. If the roots differ, attach the smaller tree under the larger one and decrement components.
  4. Return components.

find uses path halving and unions are by size, so each operation costs O(α(n)) amortized, where α is the inverse Ackermann function (at most 4 for any realistic n). Union-Find works directly on the edge list, with no adjacency list to build.

Implementation

Python:

from typing import List


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

        def find(x: int) -> int:
            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:                 # same component already: no change
                continue
            if size[ra] < size[rb]:      # union by size
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
            components -= 1              # two components became one
        return components

Java:

class Solution {
    private int[] parent, size;

    public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        int components = n;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) continue;               // same component already
            if (size[ra] < size[rb]) {            // union by size
                int t = ra; ra = rb; rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            components--;                         // two components became one
        }
        return components;
    }

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

Go:

func countComponents(n int, edges [][]int) int {
    parent := make([]int, n)
    size := make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]] // path halving
            x = parent[x]
        }
        return x
    }

    components := n
    for _, e := range edges {
        ra, rb := find(e[0]), find(e[1])
        if ra == rb {
            continue // same component already: no change
        }
        if size[ra] < size[rb] { // union by size
            ra, rb = rb, ra
        }
        parent[rb] = ra
        size[ra] += size[rb]
        components-- // two components became one
    }
    return components
}

JavaScript:

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
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;           // same component already
        if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; // union by size
        parent[rb] = ra;
        size[ra] += size[rb];
        components--;                      // two components became one
    }
    return components;
};

C#:

public class Solution {
    private int[] parent, size;

    public int CountComponents(int n, int[][] edges) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        int components = n;
        foreach (var e in edges) {
            int ra = Find(e[0]), rb = Find(e[1]);
            if (ra == rb) continue;                  // same component already
            if (size[ra] < size[rb]) (ra, rb) = (rb, ra); // union by size
            parent[rb] = ra;
            size[ra] += size[rb];
            components--;                            // two components became one
        }
        return components;
    }

    private int Find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];           // path halving
            x = parent[x];
        }
        return x;
    }
}

C++:

#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);   // each node is its own set
        setSize.assign(n, 1);

        int components = n;
        for (const auto& e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) continue;              // same component already
            if (setSize[ra] < setSize[rb]) swap(ra, rb); // union by size
            parent[rb] = ra;
            setSize[ra] += setSize[rb];
            components--;                        // two components became one
        }
        return components;
    }

private:
    vector<int> parent, setSize;

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

Complexity Analysis

  • Time: O(n + e * α(n)). Initializing the arrays is O(n), and each of the e edges does two find calls at O(α(n)) amortized each.
  • Space: O(n) for parent and size. No adjacency list is needed.

Key Insights

  • Each unvisited start node is a new component: a full traversal from it claims the whole component, so the outer loop counts components exactly.
  • Components = n - successful unions: every merge of two different sets removes exactly one component.
  • Redundant edges are harmless: an edge inside an existing component (a cycle edge) is skipped by Union-Find and simply finds visited nodes in BFS.
  • Isolated nodes count: nodes that appear in no edge are still components, which is why you loop over all n nodes rather than over the edges.

Edge Cases

  1. No edges: the answer is n.
  2. Single node: the answer is 1.
  3. One big cycle: still one component. Extra edges do not add components.
  4. Isolated nodes mixed with groups: for example n = 5, edges = [[0,1]] gives 4.
  5. Long chain (0-1-2-...-1999): one component. The iterative BFS and iterative find avoid deep recursion.

Common Mistakes

  1. Counting only nodes that appear in edges: isolated nodes are components too.
  2. Adding each edge in one direction only: for BFS on an undirected graph, add both a -> b and b -> a.
  3. Comparing nodes instead of roots in Union-Find: parent[a] == parent[b] is not the same as find(a) == find(b).
  4. Decrementing the count on every edge: only edges that merge two different roots reduce it.
  5. Recursive DFS on a long chain: a 2000-node chain already exceeds Python’s default recursion limit of 1000. An iterative BFS or an explicit stack is safe in every language.

Interview Tips

  1. Mention both approaches. BFS/DFS is the most familiar. Union-Find fits naturally because the input is an edge list and it also supports edges arriving one at a time.
  2. Explain the “n minus successful unions” idea clearly. It is the core of the Union-Find solution.
  3. If asked about complexity, explain path compression and union by size and what α(n) means in practice.
  4. Connect it to Number of Islands: that problem is the same component counting on an implicit grid graph.

Follow-up Questions

  1. Edges added over time: Union-Find answers “how many components now?” after each edge in near-constant time.
  2. Edges removed over time: Union-Find cannot split sets. Process the removals in reverse as additions (offline), or use a dynamic connectivity structure.
  3. Size of the largest component: keep size per root and track the maximum on each union.
  4. Is the graph a single tree? That is Graph Valid Tree: exactly one component and exactly n - 1 edges.