4.20.11 — Number of Connected Components in an Undirected Graph

LeetCode 323 · Medium · ★ Blind 75

The problem

Given n nodes numbered 0 to n − 1 and a list of undirected edges, count the connected components.

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

The pattern

Two clean solutions, and this is the best problem in the chapter for seeing the difference between them.

Union-find: start with n separate components. Every edge that joins two different components reduces the count by one. Edges within a component change nothing.

DFS or BFS: loop over the nodes; when you find one that has not been visited, that is a new component, so count it and flood everything reachable from it.

The second is 4.20.1 Number of Islands with an adjacency list instead of a grid.

Solution 1 — union-find

Python

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        size = [1] * n
        components = n                        # everything starts separate

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

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                continue                      # already together — no change
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
            components -= 1                   # two groups became one

        return components

TypeScript

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  let components = n;

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  for (const [a, b] of edges) {
    let ra = find(a), rb = find(b);
    if (ra === rb) continue;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
    components--;
  }

  return components;
}

Start the count at n and decrement on each successful merge. That is much cleaner than counting distinct representatives at the end, and it needs no second pass.

An edge inside an existing component does nothing. That is the continue, and it is why duplicate or redundant edges are harmless.

Solution 2 — DFS

Python

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)                  # undirected → both directions

        seen = [False] * n

        def dfs(x: int):
            seen[x] = True
            for nxt in adj[x]:
                if not seen[nxt]:
                    dfs(nxt)

        count = 0
        for i in range(n):
            if not seen[i]:
                count += 1                    # a new component
                dfs(i)

        return count

Both directions must be added for an undirected graph. Forgetting the second is a common bug that silently produces too many components.

The outer loop is what handles a disconnected graph. A single DFS only reaches one component; looping over every node is what finds the rest — exactly the structure of the island count.

Which to use

Both are effectively O(V + E). The choice is about when the edges arrive:

	union-find	DFS / BFS
all edges known up front	fine	simpler
edges arriving one at a time	natural	must re-run from scratch
need the count after every edge	O(\alpha) per edge	O(V+E) per edge
need the actual members of a component	extra work	falls out of the traversal
need a path between two nodes	cannot do it	falls out

Union-find answers "are these connected" and nothing else, but it answers it incrementally. DFS tells you far more — the path, the members, the structure — but it starts from nothing every time.

Say that trade if asked which you would choose; it is the real content of the question.

Complexity

Union-find: O(V + E \cdot \alpha(V)), effectively O(V + E). Space O(V).

DFS: O(V + E) time, O(V + E) space for the adjacency list.

Where this goes next

• Graph Valid Tree — one component and exactly n − 1 edges. 4.20.12.
• Number of Provinces (LeetCode 547) — the identical problem given as an adjacency matrix.
• Accounts Merge — union accounts sharing an email, then group by representative. A good example of union-find where the "nodes" are strings and need mapping to indices first.
• Most Stones Removed — union stones sharing a row or column; the answer is stones − components.
• Kruskal's MST — sorts edges and unions the ones that join different components. 4.21.

The pattern in the last two is worth naming: the answer is often n − components. When each merge removes one thing, counting merges and counting components are the same calculation.

What the interviewer will push on

"Union-find or DFS?" Give the incremental-versus-batch trade rather than a preference.

"Why start the count at n?" Every node begins as its own component; each merge removes one.

"What if an edge appears twice?" Harmless — the second time the nodes are already connected and nothing changes.

"What if the graph were directed?" Connected components stop being well defined; you would want strongly connected components, which needs Tarjan's or Kosaraju's algorithm. Naming one is enough.

"How would you list the members of each component?" Group nodes by find(x) in a map, or collect them during the DFS.

One thing to volunteer: say that this is the island count with an adjacency list instead of a grid. Collapsing two problems into one is the point of learning the pattern.

Next: 4.20.12 Graph Valid Tree — two conditions, and the trap of checking only one.