Connected Components

Medium

Count how many traversals it takes

Problem

Count the number of connected components in an undirected graph.

In simple words

Count connected groups of cities with DFS or union-find — each group is one province.

The idea

Start a traversal from each unvisited vertex; each one sweeps up exactly one component. The number of traversals you had to start is the number of components.

The trick

The outer loop over vertices is what handles disconnection.
DFS, BFS or union-find all work; the count is the same.
O(V + E).

←→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.