Number of Connected Components

Count separate groups in an undirected graph.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Number of Connected Components: Each unseen outer-loop vertex starts exactly one DFS and marks exactly one previously uncounted connected component.

Input and goalCount separate groups in an undirected graph.

Build the graph and initializeFor 6 nodes and edges [[0,1],[0,2],[3,4]], build both directions. Start with seen = {}, components = 0.

012

10

20

34

43

5none

queueempty

Recognize it

Use it when an undirected graph may contain multiple disconnected groups, including isolated vertices, and the task asks how many maximal reachable groups exist.

Keep true

After processing outer-loop starts below the current index, every vertex in their components is seen and components equals the number of DFS launches. A seen vertex can never launch another count.

Reuse it

A global visited set partitions a graph: every new search root contributes one component and consumes all vertices that must not contribute again. This transfers to islands, provinces, and cluster counting.

Pattern: DFS from every unseen node.

Simple idea: Every unseen node starts one new component. DFS marks its full group, so no node in that group starts another component.

def count_components(node_count: int, edges: list[list[int]]) -> int:
   graph = [[] for _ in range(node_count)]
   for first, second in edges:
      graph[first].append(second)
      graph[second].append(first)

   seen: set[int] = set()
   components = 0
   for start in range(node_count):
      if start in seen:
         continue

      components += 1
      seen.add(start)
      stack = [start]
      while stack:
         for neighbor in graph[stack.pop()]:
            if neighbor not in seen:
               seen.add(neighbor)
               stack.append(neighbor)
   return components

Cost: Close to $O(V+E)$ time and $O(V)$ space.