Connected Components: Adjacency DFS Pattern

Learning Outcome

After this lesson, you should be able to build an adjacency list, mark visited nodes, and count disconnected graph groups.

Problem Statement

Given n nodes labeled from 0 to n

• 1 and undirected edges, return the number of connected components.

Brute Force Approach

For every node, scan the whole edge list to discover neighbors. This repeats work and makes traversal harder to reason about.

Optimized Approach

Build the adjacency list once. For each unseen node, start DFS and mark its whole component.

Exact Pseudocode

build adjacency list from edges
seen = array of false
components = 0
for node from 0 to n - 1:
  if seen[node] is false:
    components += 1
    dfs(node)
return components

dfs(node):
  mark node as seen
  for neighbor in adj[node]:
    if seen[neighbor] is false:
      dfs(neighbor)
  

Reference Code

class Solution:
    def countComponents(self, n, edges):
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        seen = [False] * n

        def dfs(node):
            seen[node] = True
            for nei in adj[node]:
                if not seen[nei]:
                    dfs(nei)

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

Sample Dry Run

Complexity

Edge Cases

• Isolated nodes count as their own components.
• Repeated edges should not start new components.
• Empty edge list with n nodes returns n.

Interview Checklist

• Build adjacency for both directions.
• Mark a node before visiting its neighbors.
• Increment the answer only when starting from an unseen node.

FAQs