Module 19 · Graph Traversal and Connected Components

184. Count Graph Components

Foundation · Download this solution · All solutions and shared helpers

Problem

Count connected components in an undirected adjacency-list graph whose vertices are 0 through n-1. Both directions of every edge are represented. Isolated vertices count as components, and an empty graph returns zero. Do not change the graph.

Examples

Example 1

graph_components([[1],[0],[3],[2],[]])
=> 3

Two connected pairs and one isolated vertex form three components.

Example 2

graph_components([])
=> 0

The empty graph has no components.

Example 3

graph_components([[],[],[]])
=> 3

Every isolated vertex is its own component.

Reveal the worked solution and reasoning

Why this mechanism works

One traversal consumes one entire component. Scan all vertices outside that traversal; every still-unseen vertex begins a new component. Keep the visited set across traversals so a component is counted only at its first encountered member.

State and boundaries

seen contains the union of completed components and the currently explored one. count increases only when an unseen start is chosen.

Protocol

Scan every vertex.
Skip discovered vertices.
Increment count for a new start.
Mark it and consume its entire component with DFS.
Continue the outer scan.

Visualization

0--1    2--3    4
outer starts: 0, then 2, then 4
component count: 1 -> 2 -> 3

Python implementation

def graph_components(adj):
    seen, count = set(), 0
    for start in range(len(adj)):
        if start in seen:
            continue
        count += 1
        seen.add(start)
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
    return count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

graph_components([[1],[0],[3],[2],[]])

L2 graph_components: seen, count = set(), 0
adj=[[1], [0], [3], [2], []]; seen=set(); count=0

L3 graph_components: for start in range(len(adj)):
adj=[[1], [0], [3], [2], []]; seen=set(); count=0; start=0

L6 graph_components: count += 1
adj=[[1], [0], [3], [2], []]; seen=set(); count=1; start=0

L7 graph_components: seen.add(start)
adj=[[1], [0], [3], [2], []]; seen={0}; count=1; start=0

L8 graph_components: stack = [start]
adj=[[1], [0], [3], [2], []]; seen={0}; count=1; start=0; stack=[0]

L10 graph_components: u = stack.pop()
adj=[[1], [0], [3], [2], []]; seen={0}; count=1; start=0; stack=[]; u=0

L11 graph_components: for v in adj[u]:
adj=[[1], [0], [3], [2], []]; seen={0}; count=1; start=0; stack=[]; u=0; v=1

L13 graph_components: seen.add(v)
adj=[[1], [0], [3], [2], []]; seen={0, 1}; count=1; start=0; stack=[]; u=0; v=1

... 16 intermediate state changes omitted ...

L6 graph_components: count += 1
adj=[[1], [0], [3], [2], []]; seen={0, 1, 2, 3}; count=3; start=4; stack=[]; u=3; v=2

L7 graph_components: seen.add(start)
adj=[[1], [0], [3], [2], []]; seen={0, 1, 2, 3, 4}; count=3; start=4; stack=[]; u=3; v=2

L8 graph_components: stack = [start]
adj=[[1], [0], [3], [2], []]; seen={0, 1, 2, 3, 4}; count=3; start=4; stack=[4]; u=3; v=2

L10 graph_components: u = stack.pop()
adj=[[1], [0], [3], [2], []]; seen={0, 1, 2, 3, 4}; count=3; start=4; stack=[]; u=4; v=2

Result: 3. Two connected pairs and one isolated vertex form three components.

graph_components([])

L2 graph_components: seen, count = set(), 0
adj=[]; seen=set(); count=0

Result: 0. The empty graph has no components.

Why the solution is correct

Undirected reachability from a start is exactly its component. The inner traversal discovers all and only that component. Later scans skip its vertices, while every other component eventually supplies an unseen start, so each component is counted once.

Time and space

O(V+E) time and O(V) auxiliary space.

Common mistakes

Resetting seen for each start counts a component repeatedly. Applying this directly to directed graphs does not compute strongly connected components.

Reasoning card

State: seen contains the union of completed components and the currently explored one. count increases only when an unseen start is chosen.

Invariant: Every visited node belongs to exactly one counted component.

Decision to rehearse: Outer node scan discovers components; inner traversal consumes one.

Finish: Continue the outer scan

Transfer exercise

Return each component's member list as well as the count.