Number of Connected Components

Given n nodes and a list of undirected edges, return the number of connected components in the graph.

Example

Input: n = 5, edges (0,1) (1,2) (3,4) Output: 2

Approach

A Union-Find (disjoint set) structure tracks which nodes are already connected without needing to re-traverse the graph each time. Start with n separate components; every successful union of two previously-unconnected nodes reduces the component count by one. This is the standard tool for "are these two things connected" questions, especially when edges arrive one at a time.

Walkthrough

1class UnionFind:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.rank = [0]*n
5        self.components = n
6    def find(self, x):
7        if self.parent[x] != x:
8            self.parent[x] = self.find(self.parent[x])
9        return self.parent[x]
10    def union(self, a, b):
11        ra, rb = self.find(a), self.find(b)
12        if ra == rb:
13            return False
14        if self.rank[ra] < self.rank[rb]:
15            ra, rb = rb, ra
16        self.parent[rb] = ra
17        if self.rank[ra] == self.rank[rb]:
18            self.rank[ra] += 1
19        self.components -= 1
20        return True

Input format

Line 1: n (number of nodes, labeled 0..n-1) Line 2: number of edges E Next E lines: a b

Print the number of connected components.