Problem statement

You are given n nodes labelled 0 through n - 1 and a list of undirected edges, where edges[i] = [a, b] joins nodes a and b.

Return the number of connected components in the graph.

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= n <= 40
• 0 <= edges.length <= 60
• There are no duplicate edges and no self-loops.

Hints for Number of Connected Components in an Undirected Graph

1. Hint 1

   Start from n components and merge as you process edges.

2. Hint 2

   Union-find with path compression makes each merge nearly constant time.

3. Hint 3

   Every edge that joins two different roots reduces the component count by one.

How to solve Number of Connected Components in an Undirected Graph

Start with n singleton components and union along every edge; each edge that joins two different roots merges two components.

Approach

1. Initialise parent[i] = i and components = n.
2. For each edge, find both roots; if they differ, link them and decrement components.
3. Return components.

Why it works

Union-find maintains the partition of nodes into connected sets exactly; an edge inside an existing set changes nothing, an edge across sets merges them. Path compression keeps each find near-constant.

Complexity

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

Pitfalls

• A DFS/BFS counting how many times a fresh start is needed works equally well.

Reference solution

Python

def countComponents(n: int, edges) -> int:
    parent = list(range(n))

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

    components = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            components -= 1
    return components

Java

public static int countComponents(int n, int[][] edges) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int components = n;
    for (int[] e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            components--;
        }
    }
    return components;
}

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

C++

static int findRoot(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    int components = n;
    for (const auto& e : edges) {
        int a = findRoot(parent, e[0]);
        int b = findRoot(parent, e[1]);
        if (a != b) {
            parent[a] = b;
            components--;
        }
    }
    return components;
}

JavaScript

var countComponents = function(n, edges) {
    const parent = [];
    for (let i = 0; i < n; i++) parent.push(i);
    const find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    let components = n;
    for (let i = 0; i < edges.length; i++) {
        const a = find(edges[i][0]);
        const b = find(edges[i][1]);
        if (a !== b) {
            parent[a] = b;
            components--;
        }
    }
    return components;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium