Number of Connected Components in an Undirected Graph

Problem

You have an undirected graph with n nodes labeled 0 to n - 1. You’re given the number n and a list edges, where each edges[i] = [a, b] is an undirected edge connecting nodes a and b.

Return the number of connected components in the graph — that is, the number of maximal groups of nodes such that every node in a group is reachable from every other node in the same group, and no edge crosses between groups.

Examples

• n = 5, edges = [[0,1],[1,2],[3,4]] → 2 — {0,1,2} form one component and {3,4} the other.
• n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] → 1 — the edges chain all five nodes together.
• n = 4, edges = [] → 4 — with no edges, every node is its own component.

The first example has two components: {0,1,2} and {3,4}.

graph LR
  0 --- 1
  1 --- 2
  3 --- 4

Constraints

• 1 <= n <= 2000
• 0 <= len(edges) <= n * (n - 1) / 2
• No self-loops and no duplicate edges; each edges[i] = [a, b] has a != b.

Think about it first

TL;DR

Count how many times a fresh traversal starts (DFS/BFS), or union every edge and count roots (union-find) — O(n + E) time, O(n + E) space.

Approach 1 — DFS flood fill from each unvisited node

Starting a traversal at an unvisited node and marking everything reachable covers exactly one component. So the answer is the number of nodes from which you have to start a new traversal. Build an adjacency list, then loop over nodes; each unvisited node triggers one DFS and increments the count.

def countComponents(n: int, edges: list[list[int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)

    visited = [False] * n

    def dfs(node: int) -> None:
        visited[node] = True
        for nxt in adj[node]:
            if not visited[nxt]:
                dfs(nxt)

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

Walkthrough (n = 5, edges = [[0,1],[1,2],[3,4]]): node 0 unvisited → count 1, DFS marks 0,1,2. Nodes 1,2 already visited. Node 3 unvisited → count 2, DFS marks 3,4. Node 4 visited. Result 2.

Complexity: each node and edge is touched a constant number of times → O(n + E) time, O(n + E) space (adjacency list + recursion stack). BFS with an explicit queue is identical in cost and avoids Python’s recursion-depth limit on long chains.

Approach 2 — BFS variant

The same “one traversal per component” logic works iteratively. Prefer BFS when the graph might contain a very long chain (e.g. 2000 nodes in a line) that would overflow Python’s default recursion limit; DFS is fine when depth is bounded and you want the shorter code.

from collections import deque

def countComponents(n: int, edges: list[list[int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)

    visited = [False] * n
    count = 0
    for start in range(n):
        if visited[start]:
            continue
        count += 1
        queue = deque([start])
        visited[start] = True
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    queue.append(nxt)
    return count

Complexity: O(n + E) time, O(n + E) space.

Approach 3 — Union-Find (disjoint-set union)

Components are equivalence classes under “connected by a path.” Union-find maintains those classes directly: begin with n singletons and union the endpoints of every edge. Every successful union (merging two different sets) reduces the component count by one. Union-find is the disjoint-set data structure that supports near-O(1) find (which group is x in?) and union (merge two groups) using path compression and union by rank/size.

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

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

    def union(a: int, b: int) -> bool:
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                     # already in the same set
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        rank[ra] += rank[rb]
        return True

    for a, b in edges:
        if union(a, b):
            count -= 1
    return count

Walkthrough (n = 5, edges = [[0,1],[1,2],[3,4]]): start count 5. Union(0,1) merges → 4. Union(1,2) merges → 3. Union(3,4) merges → 2. Result 2.

Complexity: with path compression and union by rank, each operation is effectively O(α(n)) (inverse Ackermann, ≈ constant) → O(n + E·α(n)) time, O(n) space. No adjacency list needed.

Common pitfalls

• Forgetting the graph is undirected — add both a→b and b→a to the adjacency list, or a whole half of the graph disappears.
• Counting edges instead of starts. The component count is how many times you begin a new traversal, not how many nodes/edges you process.
• Skipping the “already unioned” check. If you decrement the count on every edge blindly, cycles (extra edges within one component) undercount.
• Deep recursion. A 2000-node path recursing in DFS can hit Python’s recursion limit — prefer BFS or union-find for adversarial chains.

Pattern takeaway

Connected-components counting has two canonical tools: DFS/BFS flood fill (one traversal per component) and union-find (union each edge, count distinct roots). Reach for union-find when edges arrive incrementally or you also need to detect cycles cheaply; reach for DFS/BFS when you already have (or want) the adjacency list, or need the actual component membership. Both are linear-ish and interview-standard.