Number of Provinces

The problem. There are n cities. isConnected[i][j] is 1 when city i and city j are joined by a direct road, 0 otherwise. A province is a group of cities that can reach each other, directly or through other cities, and no city outside the group. Return the number of provinces.

Example

isConnected = [[1,1,0],[1,1,0],[0,0,1]]   ->  2     (cities 0 and 1 together; 2 alone)
isConnected = [[1,0,0],[0,1,0],[0,0,1]]   ->  3     (no roads: every city alone)
isConnected = [[1,1,0],[1,1,1],[0,1,1]]   ->  1     (0-1 and 1-2: one chain)

The idea: count the pieces of the graph

Cities are vertices and roads are edges, so a province is a connected component. This time the graph comes as an adjacency matrix: row i lists every city, with 1 under the ones joined to i. Counting components is the same move as counting islands — start a walk from each city nobody has reached yet, and count the walks.

1. DFS from every unvisited city

1function findCircleNum(isConnected) {2  const n = isConnected.length;3  const visited = new Array(n).fill(false);4  const visit = (city) => {5    visited[city] = true;6    for (let other = 0; other < n; other++) {7      if (isConnected[city][other] === 1 && !visited[other]) visit(other);   // a road to someone new8    }9  };10  let provinces = 0;11  for (let city = 0; city < n; city++) {12    if (!visited[city]) {                 // no walk has reached this city: a new province13      provinces++;14      visit(city);                        // mark every city it can reach15    }16  }17  return provinces;18}

Time O(n²), space O(n). Each city is visited once, and visiting it reads its whole row of the matrix — n cells. The visited array and the recursion hold at most n cities.

2. Union-Find: merge cities into groups

A completely different way to count groups, and a preview of Pattern 7. Start with every city as its own group, so there are n provinces. Then look at each road: if its two cities are in different groups, merge the groups — one province fewer. Each group has a leader; find(x) follows parent links up to it.

1function findCircleNum(isConnected) {2  const n = isConnected.length;3  const parent = Array.from({ length: n }, (_, i) => i);   // every city leads its own group4  const find = (x) => {5    while (parent[x] !== x) {6      parent[x] = parent[parent[x]];      // path halving: point closer to the leader as we go7      x = parent[x];8    }9    return x;10  };11  let provinces = n;12  for (let i = 0; i < n; i++) {13    for (let j = i + 1; j < n; j++) {     // each road once (the matrix is symmetric)14      if (isConnected[i][j] !== 1) continue;15      const a = find(i), b = find(j);16      if (a !== b) {17        parent[a] = b;                    // merge the two groups...18        provinces--;                      // ...so there is one province fewer19      }20    }21  }22  return provinces;23}

Time O(n² log n) at worst, space O(n). Reading the matrix is O(n²); with path halving each find is at most O(log n) and usually close to constant. Pattern 7 adds union by rank, which makes every operation nearly O(1).

Comparing the approaches

Here DFS is simpler and at least as fast, because every road is known up front. Union-Find wins when roads arrive one at a time and you must report the count after each — no walk has to be redone.

Edge cases to test

Variations