Number of Connected Components in an Undirected Graph

medium
GraphsGraphDepth-First SearchUnion-Find

Given n nodes labeled from 0 to n - 1 and a list of undirected edges where each edge [a, b] connects nodes a and b, find the number of connected components in the graph.

A connected component is a maximal set of nodes such that there is a path between every pair of nodes in the set. Isolated nodes with no edges each form their own connected component.

Examples

Example 1

  • Input: n = 5, edges = [[0,1],[1,2],[3,4]]
  • Output: 2
  • Explanation: The graph has two connected components: {0, 1, 2} and {3, 4}.

Example 2

  • Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
  • Output: 1
  • Explanation: All nodes are connected in a single component.

Example 3

  • Input: n = 4, edges = []
  • Output: 4
  • Explanation: With no edges, each node is its own connected component.

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a, b < n
  • a != b
  • There are no duplicate edges.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

DFS Component Counting

Intuition

We build an adjacency list and iterate through all nodes. For each unvisited node, we start a DFS to visit all nodes in its connected component and increment a component counter. DFS naturally explores the entire connected component from any starting node by following edges to unvisited neighbors. The number of times we initiate a new DFS equals the number of connected components, since each DFS fully explores one component before we search for the next unvisited node.

Algorithm

  1. Build an adjacency list from the edges.
  2. Create a visited set and initialize a component counter to 0.
  3. Iterate through nodes 0 to n-1. For each unvisited node, increment the counter and run DFS.
  4. In DFS, mark the current node as visited and recursively visit all unvisited neighbors.
  5. After all nodes have been processed, return the component counter.
TimeO(V + E) where V is the number of nodes and E is the number of edgesSpaceO(V + E) for the adjacency list and visited set

Code (C++ · Java · Python · Go)

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

        vector<bool> visited(n, false);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                dfs(graph, visited, i);
            }
        }

        return count;
    }

private:
    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }
};
Java 21
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[] visited = new boolean[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                dfs(graph, visited, i);
            }
        }

        return count;
    }

    private void dfs(List<List<Integer>> graph, boolean[] visited, int node) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor);
            }
        }
    }
}
Python 3.12
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)

        visited = set()
        count = 0

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        for i in range(n):
            if i not in visited:
                count += 1
                dfs(i)

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

    visited := make([]bool, n)
    count := 0

    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

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

    return count
}
Approach 2

Union-Find

Intuition

Union-Find treats each node as its own component initially, then merges components as we process edges. For each edge, we find the roots of both endpoints. If they belong to different components, we union them and decrement the component count. Path compression and union by rank keep the operations nearly constant time. This approach is particularly intuitive for connectivity problems because each union operation directly corresponds to connecting two previously separate groups of nodes.

Algorithm

  1. Initialize a parent array where each node is its own parent, a rank array, and set the component count to `n`.
  2. For each edge `[a, b]`, find the root of `a` and the root of `b`.
  3. If the roots are different, union them (attach the smaller-rank tree under the larger-rank root) and decrement the component count.
  4. If the roots are the same, skip the edge (nodes are already connected).
  5. Return the final component count.
TimeO(E * alpha(V)) which is nearly O(E), where alpha is the inverse Ackermann functionSpaceO(V) for the parent and rank arrays

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> parent(n);
        vector<int> rank(n, 0);
        iota(parent.begin(), parent.end(), 0);
        int count = n;

        for (auto& e : edges) {
            int rootA = find(parent, e[0]);
            int rootB = find(parent, e[1]);

            if (rootA != rootB) {
                if (rank[rootA] < rank[rootB]) swap(rootA, rootB);
                parent[rootB] = rootA;
                if (rank[rootA] == rank[rootB]) rank[rootA]++;
                count--;
            }
        }

        return count;
    }

private:
    int find(vector<int>& parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
};
Java 21
class Solution {
    private int[] parent;
    private int[] rank;

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

        int count = n;

        for (int[] e : edges) {
            int rootA = find(e[0]);
            int rootB = find(e[1]);

            if (rootA != rootB) {
                if (rank[rootA] < rank[rootB]) {
                    int temp = rootA;
                    rootA = rootB;
                    rootB = temp;
                }
                parent[rootB] = rootA;
                if (rank[rootA] == rank[rootB]) rank[rootA]++;
                count--;
            }
        }

        return count;
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}
Python 3.12
from typing import List


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

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        count = n
        for a, b in edges:
            root_a, root_b = find(a), find(b)
            if root_a != root_b:
                if rank[root_a] < rank[root_b]:
                    root_a, root_b = root_b, root_a
                parent[root_b] = root_a
                if rank[root_a] == rank[root_b]:
                    rank[root_a] += 1
                count -= 1

        return count
Go 1.26
func countComponents(n int, edges [][]int) int {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := range parent {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    count := n
    for _, e := range edges {
        rootA, rootB := find(e[0]), find(e[1])
        if rootA != rootB {
            if rank[rootA] < rank[rootB] {
                rootA, rootB = rootB, rootA
            }
            parent[rootB] = rootA
            if rank[rootA] == rank[rootB] {
                rank[rootA]++
            }
            count--
        }
    }

    return count
}

Frequently asked questions

What is the optimal time complexity of Number of Connected Components in an Undirected Graph?

The most efficient approach in this guide ("Union-Find") runs in O(E * alpha(V)) which is nearly O(E), where alpha is the inverse Ackermann function time and uses O(V) for the parent and rank arrays extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Number of Connected Components in an Undirected Graph use?

Number of Connected Components in an Undirected Graph is a medium-level Graphs problem involving Graph, Depth-First Search, Union-Find. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Number of Connected Components in an Undirected Graph be solved without extra space?

The most space-efficient approach in this guide uses O(V) for the parent and rank arrays extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(V + E) for the adjacency list and visited set, while the optimized version uses O(V) for the parent and rank arrays.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Graph Valid TreeNumber of Islands
Loading editor...
Input
n=
5
edges=
[[0,1],[1,2],[3,4]]
Expected Output
2