Number of Connected Components

MediumUnion-Find (DSU)Blind 75MidOpen on LeetCodeUpdated Nov 11, 2026

You're 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. A connected component is a group of nodes that can all reach one another through edges, with no edge leading outside the group. Return the number of connected components. A node with no edges is a component by itself.

Examples

n = 5, edges = [[0,1],[1,2],[3,4]] returns 2

Two separate groups: 0, 1, 2 and 3, 4.

Nodes 0, 1 and 2 are linked in a chain, and 3 and 4 are linked to each other. Nothing joins the two groups, so there are 2 components.

n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] returns 1

The edges chain all five nodes together, so there is 1 component.

n = 4, edges = [[0,1]] returns 3

Nodes 2 and 3 have no edges, so each counts on its own.

0 and 1 form one component. Nodes 2 and 3 have no edges, so each is a component of its own, for 3 in total.

Constraints

1 <= n <= 2000
1 <= edges.length <= 5000

Hints

Hint 1

How can you merge two endpoints of an edge so that 'are these in the same group?' is a constant-time check?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Start with every node in its own group, so the count begins at n. For each edge, find the root of each endpoint's group. If the roots differ, merge the groups by pointing one root at the other and decrement the count; if they match, the edge adds nothing new. find shortens paths as it walks, keeping chains flat. With path compression alone (no union by rank), each find is O(log n) amortized, so O(n + E log n) time and O(n) space.

Time

O(n + E log n)

Space

O(n)

Pitfall

Decrementing the count for every edge instead of only when the roots differ: an edge inside an existing group, like the third side of a triangle, makes you undercount. Compare roots, not the endpoints' immediate parents.

Solutions

class Solution {
    public 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 ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra != rb) {
                parent[ra] = rb;
                components--;
            }
        }
        return components;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}

class Solution:
    def countComponents(self, 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