Connected Components in Undirected Graph

BFS — Component Discovery

LeetCode 323 • Medium • Graphs

Input: n = 5, edges = [[0,1],[1,2],[3,4]] → Output: 2
For each unvisited node, run BFS to discover its entire connected component. Count how many BFS calls it takes.

Time O(V+E) visit each vertex & edge once

Space O(V) visited set + queue

Visited: 0/5 Queue: 0 Components: 0

Processing

In Queue

Component 1

Component 2

Unvisited

Queue

empty

Visited

{ }

Count

Speed:

Ready

Press Play to watch BFS discover connected components, or Step to advance one operation at a time.
Each unvisited node triggers a new BFS, discovering one complete component.

✎ Whiteboard

Size: 3

⌨ Type It — Build Muscle Memory

Practice until you don't need to look. Use the guide comments below as scaffolding. Type the full implementation in the editor. The green highlights are the nuances to burn into memory.

# ─── CONNECTED COMPONENTS (LeetCode 323) ───

# Pattern: BFS per unvisited node

# Time: O(V+E) Space: O(V)

# 1. Import: from collections import deque

# 2. Define: countComponents(self, n, edges)

# 3. BFS helper (closure over visited):

# def bfs(start):

# queue = deque([start])

# visited.add(start) ← mark BEFORE loop

# while queue:

# current = queue.popleft()

# for neighbor in graph[current]:

# if neighbor not in visited:

# visited.add(neighbor)

# queue.append(neighbor)

# 4. Build adjacency list:

# graph = {i: [] for i in range(n)}

# for u, v in edges:

# graph[u].append(v) ← bidirectional!

# graph[v].append(u) ← don't forget this

# 5. Main loop:

# count = 0

# visited = set()

# for node in range(n):

# if node not in visited:

# count += 1

# bfs(node)

# return count

# Key: each BFS discovers ONE complete component

# Vars: graph (dict), queue (deque), visited (set), count

▼ your implementation ▼

Verify your solution: