Given an undirected graph as an adjacency list, return the number of nodes in its largest connected component.
largestComponent(graph)
Input format: a,b edge pairs separated by spaces.
a,b c,d c,e // → 3 ({c,d,e})
a,b b,c c,a d,e // → 3 ({a,b,c})
a,b // → 2
This is a small variation on counting components: instead of how many exist, you need the size of the largest one. The scanning strategy stays the same — walk every node, and whenever you find one unvisited, that's a new component.
Previously, exploring just marked nodes visited. Now the traversal needs to report a count: how many nodes did it touch? Have the exploration function return a count instead of nothing. Visiting one node is 1; for each unvisited neighbour, recursively explore and add whatever count it reports back. A neighbour already visited contributes 0 — you don't want to double-count.
Without tracking visited nodes, a cycle could cause the traversal to revisit nodes repeatedly, both looping forever and overcounting the size. Marking a node visited the instant you enter it guarantees each node contributes to the count exactly once, no matter how many cycles connect it to the rest of its component.
As you scan every node, each time you hit an unvisited one, run this size-counting exploration and compare against the largest seen so far. By the time you've scanned everything, you've measured every component once.
You could collect a list of components first, then measure each afterward — but that needs extra bookkeeping (grouping nodes) for no gain. Merging the measurement into the same traversal that discovers the component is simpler: one pass, one visited set, one running answer.
def largest_component(graph):
visited = set()
def size(node):
if node in visited:
return 0
visited.add(node)
count = 1
for nxt in graph.get(node, []):
count += size(nxt)
return count
largest = 0
for node in graph:
s = size(node)
if s > largest:
largest = s
return largest
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.