Number of Connected Components in an Undirected Graph

There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.

The nodes are numbered from 0 to n - 1.

Return the total number of connected components in that graph.

Approach

Use Union-Find to group nodes. Start with each node as its own component. For every edge, union the endpoints; if they were in different sets, reduce the component count. The final count is the answer.

Why It Works

Union-Find merges exactly the nodes that are connected by some path. Each successful union reduces the number of connected components by one. After processing all edges, the remaining set count equals the number of connected components.

Complexity

• Time: O(n + e)
• Space: O(n)

Reference Implementation (Python)

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

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

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True

        for a, b in edges:
            if union(a, b):
                count -= 1
        return count