[547] 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]

输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]

输出：3

这个也是岛屿问题的一个变种，这里我们还是考虑使用 visited 数组与 DFS 来解题。

注意到，实际上isConnected[i][j] 与 isConnected[j][i] 指的是同一件事。也就是说，我们判断省份 a、b 是否联通时，只需要判断一遍即可。

因此我们的 visited 数组可以被简化为一维数组，表示各省份是否有被遍历过。

function findCircleNum(isConnected: number[][]): number {
  let res = 0;
  const len = isConnected.length;

  const visited: boolean[] = Array(len).fill(false);

  for (let i = 0; i < len; i++) {
    if (!visited[i]) {
      res += 1;
      dfs(i);
    }
  }

  function dfs(i: number) {
    visited[i] = true;
    for (let j = 0; j < len; j++) {
      if (isConnected[i][j] === 1 && !visited[j]) {
        dfs(j);
      }
    }
  }

  return res;
}