Number of Connected Components in an Undirected Graph

Solving tips

The count equals how many times you start a fresh DFS/BFS: loop over all nodes and traverse each unvisited one, incrementing the count per new start; O(n+E).
Union-find is the clean alternative: start count at n, union each edge's endpoints, and decrement only on a successful merge (endpoints in different sets).
Build the adjacency list undirected (add both a->b and b->a), or half the graph disappears.
Pitfall: don't blindly decrement on every edge in union-find; a cycle edge (already-same root) must not reduce the count, and prefer BFS/union-find over deep recursion on a 2000-node chain.

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.

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

Hint 1

A component is a set of mutually reachable nodes. If you start a traversal at an unvisited node and mark everything you can reach, you've discovered exactly one whole component.

Hint 2

Loop over all nodes. Each time you find one that hasn't been visited yet, run a DFS or BFS from it (marking everything reachable) and add one to your count. The number of times you *start* a fresh traversal is the number of components.

Hint 3

There's a classic alternative that avoids building an adjacency list: union-find (disjoint-set union). Start with `n` separate sets and union the two endpoints of every edge. The number of distinct roots at the end is the component count.

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

The insight: starting a traversal at an unvisited node and marking everything reachable “paints” exactly one component. So the answer is the number of nodes from which you have to start a new paint. Build an adjacency list, then loop over nodes; each unvisited node triggers one DFS and bumps the count.

class Solution:
    def countComponents(self, 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 insight: the same “one traversal per component” logic works iteratively. BFS is preferred here 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 preferred when you like the shorter code and depth is bounded.

from collections import deque

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

The insight: 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.

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