LeetCode 323: Number of Connected Components in an Undirected Graph

Problem Restatement

We are given:

n
edges

There are n nodes labeled:

0 to n - 1

edges describes an undirected graph.

Return the number of connected components.

A connected component is a maximal group of nodes where every node can reach every other node in the group.

The official problem defines the graph as undirected with nodes labeled from 0 to n - 1. (github.com)

Input and Output

Item	Meaning
Input	Number of nodes `n` and undirected edges
Output	Number of connected components
Graph type	Undirected
Node labels	`0` through `n - 1`

Function shape:

def countComponents(
    n: int,
    edges: list[list[int]],
) -> int:
    ...

Examples

Example 1:

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

Graph:

0 -- 1 -- 2

3 -- 4

There are two connected groups:

{0,1,2}
{3,4}

Output:

Example 2:

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

Graph:

0 -- 1 -- 2 -- 3 -- 4

Every node is connected.

Output:

First Thought: Explore Each Group

If we start from one node and traverse all reachable nodes, we discover one complete connected component.

Then:

Pick an unvisited node.
Run DFS or BFS.
Mark all reachable nodes.
Increase component count.
Repeat.

This directly matches the definition of connected components.

Graph Representation

The graph is undirected.

So for every edge:

[a, b]

we add:

a -> b
b -> a

An adjacency list works well.

Example:

edges = [[0,1], [1,2], [3,4]]

Adjacency list:

Node	Neighbors
`0`	`[1]`
`1`	`[0,2]`
`2`	`[1]`
`3`	`[4]`
`4`	`[3]`

DFS Solution

Maintain:

visited

When we see an unvisited node, run DFS from it.

That DFS marks one whole connected component.

So every DFS call corresponds to exactly one component.

DFS Walkthrough

Use:

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

Start:

visited = {}
count = 0

Node 0 is unvisited.

Run DFS:

0 -> 1 -> 2

Now:

visited = {0,1,2}
count = 1

Node 3 is unvisited.

Run DFS:

3 -> 4

Now:

visited = {0,1,2,3,4}
count = 2

All nodes are visited.

Answer:

Algorithm

Build an adjacency list.
Create a visited set.
Initialize component count to 0.
For each node:
- If unvisited:
  - Run DFS or BFS.
  - Increment the component count.
Return the count.

Correctness

Whenever the algorithm starts DFS from an unvisited node u, the DFS visits every node reachable from u.

Because the graph is undirected, every node in the same connected component as u is reachable from u, so the DFS marks the entire component.

The DFS cannot visit nodes from another component, because no path exists between different connected components.

Therefore:

One DFS call visits exactly one connected component.
Every connected component eventually triggers exactly one DFS call.

The algorithm increments the counter once per DFS call, so the final count equals the number of connected components in the graph.

Complexity

Let:

Symbol	Meaning
`n`	Number of nodes
`m`	Number of edges

Metric	Value	Why
Time	`O(n + m)`	Every node and edge is processed once
Space	`O(n + m)`	Adjacency list and visited set

DFS Implementation

from collections import defaultdict

class Solution:
    def countComponents(
        self,
        n: int,
        edges: list[list[int]],
    ) -> int:

        graph = defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()

        def dfs(node: int) -> None:
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        components = 0

        for node in range(n):
            if node not in visited:
                dfs(node)
                components += 1

        return components

Code Explanation

Build the adjacency list.

graph = defaultdict(list)

For every undirected edge:

graph[a].append(b)
graph[b].append(a)

Track visited nodes.

visited = set()

DFS marks all reachable nodes.

def dfs(node: int) -> None:

Mark current node.

visited.add(node)

Then recursively visit neighbors.

for neighbor in graph[node]:
    if neighbor not in visited:
        dfs(neighbor)

Now scan all nodes.

for node in range(n):

If a node is unvisited, it starts a new component.

if node not in visited:

Run DFS and increase the count.

dfs(node)
components += 1

BFS Implementation

The same logic also works with BFS.

from collections import defaultdict, deque

class Solution:
    def countComponents(
        self,
        n: int,
        edges: list[list[int]],
    ) -> int:

        graph = defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()
        components = 0

        for start in range(n):
            if start in visited:
                continue

            components += 1

            queue = deque([start])
            visited.add(start)

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

        return components

Union-Find Solution

This problem is also a classic Union-Find application.

Initially every node is its own component.

For every edge:

[a, b]

merge the components containing a and b.

The remaining number of disjoint sets is the answer.

class UnionFind:

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

        self.components -= 1

class Solution:
    def countComponents(
        self,
        n: int,
        edges: list[list[int]],
    ) -> int:

        uf = UnionFind(n)

        for a, b in edges:
            uf.union(a, b)

        return uf.components

Testing

def run_tests():
    s = Solution()

    assert s.countComponents(
        5,
        [[0, 1], [1, 2], [3, 4]],
    ) == 2

    assert s.countComponents(
        5,
        [[0,1], [1,2], [2,3], [3,4]],
    ) == 1

    assert s.countComponents(
        4,
        [],
    ) == 4

    assert s.countComponents(
        1,
        [],
    ) == 1

    assert s.countComponents(
        6,
        [[0,1], [1,2], [3,4]],
    ) == 3

    assert s.countComponents(
        7,
        [[0,1], [1,2], [2,0], [3,4], [5,6]],
    ) == 3

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Two disconnected groups	Standard example
Fully connected chain	Single component
No edges	Every node isolated
Single node	Smallest graph
One isolated node plus groups	Mixed structure
Graph with cycle	Confirms cycles do not affect counting