Connected Components in Undirected Graph

Intuition

Two nodes belong to the same component exactly when a path connects them. Union-Find keeps a representative root for every set of connected nodes, so checking whether two nodes are already linked is a quick root comparison. Begin by treating each node as its own component, which gives n separate groups. Every edge that joins two nodes from different groups fuses them and reduces the number of components by one; an edge inside an existing group changes nothing. After all edges are processed, the number of surviving groups is the answer.

Algorithm walkthrough

1. 1Initialize a parent array where each node points to itself, and set a counter equal to n.
2. 2Define find(x) to follow parent pointers up to the root, compressing the path so later lookups are faster.
3. 3For each edge (a, b), locate the roots of a and b.
4. 4If the roots differ, attach one root under the other and decrement the counter.
5. 5If the roots already match, the edge lies inside a known component, so skip it.
6. 6Return the counter after every edge has been consumed.

Implementation

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        count = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                count -= 1
        return count