Easy Loop + BFS/DFS Graphs
In plain English: Count how many disconnected groups of nodes exist in a graph.
Each DFS from an unvisited node discovers one full connected component — the count of fresh traversals equals the number of components.
Prompt
Count the number of connected components in an undirected graph.
Try to write it from scratch before scrolling down.
Solution
def count_components(graph, n):
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph.get(node, []):
if nb not in visited:
dfs(nb)
for i in range(n):
if i not in visited:
# new traversal = new component
dfs(i)
count += 1
return count
# Test: {0:[1], 1:[0], 2:[3], 3:[2], 4:[]}, n=5 => 3