Number of Connected Components in an Undirected Graph

PracticeNeetCode ↗LeetCode ↗

Given n nodes labeled 0 to n - 1 and a list of undirected edges, return the number of connected components in the graph.

Example

Key Pointers

• Union-Find (disjoint set union) is the natural fit: each edge unions its two endpoints, and the distinct roots left at the end are the components.
• Path compression keeps repeated find calls close to O(1) amortized as unions accumulate.
• A plain DFS/BFS works too — start a new traversal (and increment the count) each time an unvisited node is found — but Union-Find avoids building an explicit adjacency structure.

Step-by-Step Analysis

1. Initialize a parent array where every node starts as its own parent (n separate components).
2. For each edge (a, b), find the roots of a and b; if they differ, union them (this reduces the component count by one).
3. Use path compression inside find so lookups stay fast.
4. Return the number of merges that actually happened, subtracted from the starting count of n.

Complexity

Time: O(V + E · α(V)) (α is the inverse Ackermann function, effectively constant) — Space: O(V)

Code

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

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

    def union(a: int, b: int) -> bool:
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return False
        parent[root_a] = root_b
        return True

    components = n
    for a, b in edges:
        if union(a, b):
            components -= 1

    return components

Code Explanation

How the solution above works, piece by piece.

1. Union-Find: parent[x] points toward the representative (root) of x's group. Initially every node is its own group, so there are n components.
2. find follows parent links to the root, and path halving (parent[x] = parent[parent[x]]) shortens the chain as it goes.
3. union(a, b) joins two groups by pointing one root at the other; it returns False if they were already in the same group.
4. Every successful union merges two components into one: components -= 1.
5. Nearly O(1) per edge (amortized), so about O(n + E) overall.

Visual Walkthrough

Running it on n = 5, edges = [[0, 1], [1, 2], [3, 4]]:

Video Explanation

NeetCode — Union Find, LeetCode 323