Description
Count connected components among n vertices labeled 0 through n-1, including isolated vertices.
Solution
def count_components(n, edges):
graph = [[] for _ in range(n)]
for a,b in edges:
graph[a].append(b)
graph[b].append(a)
seen = set()
count = 0
for start in range(n):
if start in seen:
continue
count += 1
seen.add(start)
stack = [start]
while stack:
for neighbor in graph[stack.pop()]:
if neighbor not in seen:
seen.add(neighbor)
stack.append(neighbor)
return countExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[4,[[0,1],[2,3]]]- Output
2
The graph contains two separate pairs.
Example 2
- Input
[3,[]]- Output
3
Each isolated vertex counts once.
Example 3
- Input
[3,[[0,1],[1,2]]]- Output
1
All three vertices share a connected chain.
Approach
Build adjacency lists and launch a stack traversal from each unseen vertex.
Time & space
O(V + E) time; O(V + E) auxiliary space for V vertices and E edges.