解題程式碼

var findCircleNum = function (isConnected) {
  const visited = new Set();
  let province = 0;

  const dfs = (i) => {
    for (let j = 0; j < isConnected[i].length; j++) {
      if (isConnected[i][j] && !visited.has(j)) {
        visited.add(j);
        dfs(j);
      }
    }
  };

  for (let i = 0; i < isConnected.length; i++) {
    if (!visited.has(i)) {
      dfs(i);
      province++;
    }
  }

  return province;
};

Union Find 解:

var findCircleNum = function (isConnected) {
  const parents = new Array(isConnected.length).fill().map((element, index) => index);

  const find = (x) => {
    if (parents[x] !== x) {
      parents[x] = find(parents[x]);
    }

    return parents[x];
  };

  const union = (x, y) => {
    parents[find(x)] = find(y);
  };

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

  let provinces = 0;
  parents.forEach((element, index) => {
    if (element === index) provinces++;
  });

  return provinces;
};

解題思路、演算法

這題用 DFS、BFS、Union Find 都可以做，用 DFS 的話，可以用一個 hashSet 記錄走過的 city，然後先遍歷 isConnected 陣列第一維陣列即可，因為第二維陣列是該 city 和其他 city 是否相連的關係。

以其中一個 test case 為例，造訪 index 0 的城市，hashSet 為 { 0 }，province 是用來記數 province 數目，加一，接著就開始 DFS 找有沒有和它相連的城市，1 能造訪。

所以造訪 index 1 的城市，hashSet 為 { 0, 1 }，因為它和 index 0 的城市相連，province 不增加，並發現沒有其他相連的城市，所以繼續遍歷 isConnected 陣列第一維陣列。

接著造訪 index 2 的城市，是沒有造訪過的城市，hashSet 為 { 0, 1, 2 }，province 加一，然後發現它和 index 3, 4 的城市相連，所以用 DFS 查找 index 3, 4 有沒有更多相連的城市。

DFS 都完成後，hashSet 為 { 0, 1, 2, 3, 4 }，接著造訪 index 5 的城市，是沒有造訪過的城市，hashSet 為 { 0, 1, 2, 3, 4, 5 }，province 加一，最終沒有其他城市要造訪，故 province = 3。

[[1, 1, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 0, 1, 1, 0, 0],
[0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 1]]

解法的時間、空間複雜度

時間複雜度: O(n^2)
空間複雜度: O(n)

參考資料

NUMBER OF PROVINCES (Leetcode) - Code & Whiteboard

DFS 作法，講得蠻清楚