Number of provinces

Medium

Connected components of a friendship matrix

Problem

Given an n x n adjacency matrix of friendships, count the number of provinces (connected friend groups).

In simple words

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

The idea

A province is a connected component, and the matrix is just a dense adjacency representation. Traverse from each unvisited city marking everyone reachable, and count the traversals.

The trick

Row i column j non-zero means an edge — treat it as adjacency.
O(n²) because reading the matrix dominates.
Union-find gives the same answer by counting distinct roots.

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