Number of Connected Components in an Undirected Graph

Difficulty: Medium Source: NeetCode

Problem

There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.

Return the total number of connected components in that graph.

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

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

Constraints:

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1) / 2

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS — for traversing and marking nodes in the same component
• Union-Find — for efficiently merging connected components

1. DFS Marking

Intuition

For each unvisited node, start a DFS that visits all connected nodes and marks them. Each DFS call from an unvisited node represents a new connected component. Count those calls.

Algorithm

1. Build adjacency list.
2. Track visited set.
3. For each node from 0 to n-1: if unvisited, increment count and run DFS to mark all connected nodes.
4. Return count.

Solution

def countComponents(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()

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

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

    return count


print(countComponents(3, [[0,1],[0,2]]))            # 1
print(countComponents(6, [[0,1],[1,2],[2,3],[4,5]])) # 2
print(countComponents(5, []))                         # 5 (all isolated)
print(countComponents(1, []))                         # 1

Complexity

• Time: O(V + E)
• Space: O(V + E)

2. Union-Find

Intuition

Initialize each node as its own component. For each edge, union the two endpoints. If they were in different components, the total component count decreases by 1. Track the count directly during union operations.

Algorithm

1. Initialize parent[i] = i, count = n.
2. For each edge (a, b): if find(a) != find(b), union them and decrement count.
3. Return count.

Solution

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

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

    def union(x, y):
        nonlocal count
        px, py = find(x), find(y)
        if px == py:
            return
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        count -= 1

    for a, b in edges:
        union(a, b)

    return count


print(countComponents(3, [[0,1],[0,2]]))             # 1
print(countComponents(6, [[0,1],[1,2],[2,3],[4,5]])) # 2
print(countComponents(5, []))                         # 5
print(countComponents(5, [[0,1],[1,2],[3,4],[2,3]])) # 1

Complexity

• Time: O(E * α(N)) — nearly O(E) with path compression + union by rank
• Space: O(N)

Common Pitfalls

Undirected edges: add both directions. In the adjacency list, each edge (a, b) must add b to graph[a] and a to graph[b]. Forgetting one direction splits connected components incorrectly.

Starting count at n. In Union-Find, start with count = n (every node is its own component) and decrement each time you successfully merge two distinct components.

DFS on isolated nodes. Nodes with no edges are still valid components. Iterating for node in range(n) ensures every node gets counted, even isolated ones.