Number of Connected Components

Medium

Traverse from each unvisited node

Problem

Count connected components in an undirected graph of n nodes and given edges.

In simple words

Count the separate groups of connected nodes with DFS or union-find.

The idea

Start a search at every vertex not yet seen; each search covers one component. Counting the searches counts the components, and union-find gives the same answer by counting distinct roots.

The trick

O(V + E) with DFS or BFS.
Union-find: components = n - number of successful unions.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output:: 2
Explanation:: Cities 0-1 form one group; city 2 is alone → 2.

Example 2

Input:: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output:: 3
Explanation:: Nobody is connected → 3 separate provinces.

Example 3

Input:: isConnected = [[1,1],[1,1]]
Output:: 1
Explanation:: Both cities linked → one province.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.