A connected component is a maximal set of nodes that can all reach each other. Two natural strategies both work: flood-fill from every unvisited node and count how many flood fills it takes (the same “how many islands” idea, applied to an adjacency-list graph instead of a grid), or track components directly with a union-find structure as edges are processed.
Running example: n = 5, edges = [[0,1],[1,2],[3,4]].
DFS / BFS Flood Fill
Time O(V + E)Space O(V + E)Build an adjacency list from the edges (undirected, so each edge is added both ways). Scan every node; each time an unvisited node is found, flood fill its whole component and count one more component found.
from collections import deque
class Solution: def countComponents(self, n: int, edges: list[list[int]]) -> int: graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) graph[b].append(a)
visited = set() components = 0
for start in range(n): if start in visited: continue components += 1 queue = deque([start]) visited.add(start) while queue: u = queue.popleft() for v in graph[u]: if v not in visited: visited.add(v) queue.append(v)
return componentsOn the example: scanning from node 0 (unvisited) triggers a BFS that reaches {0, 1, 2} via the edges (0,1) and (1,2) — one component found. Nodes 1 and 2 are now visited, so the scan skips them. Node 3 is unvisited, triggering a second BFS that reaches {3, 4} via edge (3,4) — a second component. The scan finishes at node 4 (already visited). Total: 2 components.
Why it’s correct: flood-filling from a node reaches exactly the nodes in its connected component (by definition of “connected”), and marking them visited means later flood fills only start in genuinely new components. Complexity: building the adjacency list is O(E); each node and edge is visited by exactly one flood fill → O(V + E) time, O(V + E) space for the graph and visited set.
The number of flood fills is exactly the number of connected components — the same answer the union-find solution below computes by merging groups and counting the merges instead of exploring the graph.
Union-Find
OptimalTime O(V + E)Space O(V)Skip building an adjacency list entirely. Start with n separate components (every node its own component) and process each edge with a union operation; every time an edge merges two components that were not already the same, decrement the running component count by one.
class Solution: def countComponents(self, n: int, edges: list[list[int]]) -> int: parent = list(range(n)) components = n
def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path compression x = parent[x] return x
for a, b in edges: root_a, root_b = find(a), find(b) if root_a != root_b: parent[root_a] = root_b components -= 1
return componentsWatch the mechanism that makes the whole solution work: every edge runs find on both endpoints to reach their component roots, and a merge happens only when those two roots differ — each successful merge ticks the components counter down by one, while an edge whose endpoints already share a root ticks nothing. The trace below replays the statement’s example in slow motion, then the chain variant compressed, with one redundant edge appended so the no-op case is visible.
Example 1 — statement trace, slow motion
input edges
component groups (color = component)
parent array
Start: each node is its own component — five singleton pills, each with its own root, and `components = 5`. The `parent` array reads `[0, 1, 2, 3, 4]`: for every node, `parent[i] = i` means it points at itself, so every find below is zero hops for now. Watch the counter — it ticks down exactly when an edge joins two different groups.
Every edge of the first example merges two different groups, so none is wasted: the counter walks 5 → 4 → 3 → 2 and leaves exactly the components {0, 1, 2} and {3, 4}, matching the expected output. In the second phase the four chain edges bring the counter to 1 — the statement’s second expected output — and the appended redundant edge (0, 2) is a no-op: both endpoints already share a root, so the counter stays at 1.
Why it’s correct: each successful union strictly reduces the number of distinct components by exactly one, since it merges two previously-separate groups; a union between two nodes already in the same component is a no-op that correctly leaves the count unchanged (it doesn’t create a new merge). Starting from n singleton components and applying every edge this way tracks the true component count throughout. Complexity: E union-find operations, each nearly O(1) amortized with path compression → O(V + E) time (effectively O(V + E · α(V))), and O(V) space for the parent array — no adjacency list required, which is the main saving over the flood-fill approach.