Number of Connected Components In An Undirected Graph

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 components

On 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.

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 components

Watch 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.

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.