Given an undirected graph as an adjacency list, return the number of connected components (groups of nodes that are reachable from one another).
connectedComponentsCount(graph)
Input format: a,b edge pairs separated by spaces. A node with no edges still
appears as its own component if it's an endpoint elsewhere; for this problem all
nodes come from the edge list.
a,b c,d c,e // → 2 ({a,b} and {c,d,e})
a,b b,c c,a // → 1
a,b c,d e,f // → 3
A connected component is a maximal group of nodes where every node can reach every other in the group, and none can reach anything outside it. On paper, each visually separate "blob" of connected dots is one component. You want to count the blobs.
You already have the tool to explore one component fully: a traversal (DFS or BFS) with a visited set touches every node reachable from a starting point — exactly "everything in this node's component." The new idea is what to do with that tool across the whole graph.
If you pick an unvisited node and fully explore everything reachable from it, you've identified one entire component, marking every node in it visited along the way. Any node still unvisited afterward must belong to a different component. So: scan every node, and each time you hit an unvisited one, you've found the start of a new component — increment your count, then fully explore and mark it before continuing the scan.
Since exploration marks every reachable node visited before you move on, you'll never restart a count from a node already part of a counted component. Since you scan every node, you're guaranteed to hit at least one node in every component. The count of fresh explorations exactly equals the number of components.
The number of components depends on connectivity structure, which only a traversal reveals — not a simple count of total nodes or edges. This "scan for unvisited, explore its reachable set, repeat" pattern is the backbone for follow-ups like measuring the largest component: instead of counting explorations, track how many nodes each one touches.
def connected_components_count(graph):
visited = set()
def explore(node):
if node in visited:
return
visited.add(node)
for nxt in graph.get(node, []):
explore(nxt)
count = 0
for node in graph:
if node not in visited:
count += 1
explore(node)
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.