Number of Provinces

1. Define the problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and b is connected directly with city c, then a is connected indirectly with c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected_i[j] = 1 if the ith city and the jth city are directly connected, and 0 otherwise. Return the total number of provinces. Union every direct connection, then count the distinct roots left standing.

Constraints

1 ≤ n ≤ 200
isConnected_i[j] is 1 or 0
isConnected_i[i] == 1

Example

InputisConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output2

Explanation Cities 0 and 1 are directly connected, forming one province. City 2 is its own province.

2. Visualize the solution

Union direct connections, count remaining roots

0root 0

1root 0

2root 2

Statusunion

isConnected[0][1] = 1, so union city 0 and city 1. Groups: 3 → 2.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
size[0] = 1, size[1] = 1 → size[0] is not smaller, so attach root 1 under root 0
parent[1] = 0
size[0] = 1 + 1 = 2
groups: 3 → 2

Cities 0 and 1 merge into one group anchored at root 0.

Step 1 of 3

Steps to visualize

Start every city in its own group and set the group count to n.
Scan every pair (i, j); if isConnected_i[j] is 1, union them, and if that merge combined two different groups, drop the count by one.
When the scan finishes, the count is the number of provinces.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union direct connections, count remaining roots

0root 0

1root 0

2root 2

Statusunion

isConnected[0][1] = 1, so union city 0 and city 1. Groups: 3 → 2.

What happens in this step

union(0, 1)
find(0) → 0   find(1) → 1
size[0] = 1, size[1] = 1 → size[0] is not smaller, so attach root 1 under root 0
parent[1] = 0
size[0] = 1 + 1 = 2
groups: 3 → 2

Cities 0 and 1 merge into one group anchored at root 0.

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  let groups = n;

  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return;

    if (size[rootA] < size[rootB]) {
      parent[rootA] = rootB;
      size[rootB] += size[rootA];
    } else {
      parent[rootB] = rootA;
      size[rootA] += size[rootB];
    }
    groups--;
  }

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) union(i, j);
    }
  }

  return groups;
}

Time: O(n^2 · α(n))
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`isConnected = [[1,1,0],[1,1,0],[0,0,1]]`	`2`	example from the docstring
`isConnected = [[1,0,0],[0,1,0],[0,0,1]]`	`3`	no city connects to any other
`isConnected = [[1,1,1],[1,1,1],[1,1,1]]`	`1`	every city connects directly to every other city
`isConnected = [[1]]`	`1`	smallest valid input, a single city
`isConnected = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]]`	`1`	cities only connect to their immediate neighbor, forming one long chain
`isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]`	`2`	two separate pairs of connected cities

Number of Provinces