547. 省份数量

搜索 · 07-17

题目链接：https://leetcode.cn/problems/number-of-provinces/description/

我的思路

尝试用第200题的思路，但是又理解错了题目意思，没有好好读题。这道题和第200题不一样的是，给的矩阵表示了节点之间的连接情况，而不是表示“地图”，并且在提示中也清晰说明了 isConnected[i][i] == 1以及isConnected[i][j] == isConnected[j][i] ，同时尝试用类似的题解来答，会给出错误的答案，因为一方面isConnected的意思并不是我们想象的那样，另一方面其并不能被原地修改，因此插旗法不适用，如果强制用原先的办法，就会返回矩阵里有几个1值

纠正

仍使用广度优先搜索算法，但采用递归的方法。假设矩阵有$n$个元素，意味着有$n$个城市（节点），每个节点可以有$n$个边，表示和所有城市都相连（都是朋友），最少可以有1条边，表示自己和自己相连（代表矩阵的对角元素）。这道题里，我们无法直接修改原始矩阵的值，而且直接修改没有什么意义，回顾一下之前我们做标记的初衷：为了标识这个岛屿的这个位置我们已经访问过了，已经走过，所以打标记为0或#，同时我们的算法代码能够保证一次性把所有符合条件的位置都走遍，防止我们重复走，可以类比成“染色”：从某个城市出发，把能走到的所有城市都染成已访问

在这里我们不能直接改原来的值，那么换一个思路，定义一个长度为$n$的列表，访问过的城市记录为True，不就可以了吗？无论是间接还是直接，接下来的DFS函数都能把这条链给完整找出来，同时也能把这些城市都给访问一遍，标记为True，这样就不会出现重复判断的问题了。算法过程如下：

  1. 从某个未访问的城市 i 开始。

  2. 动作：

    • 标记 i 已访问。

    • 遍历所有城市 k：

      • 如果 i 和 k 相连，且 k 没访问过 → 递归 dfs(k)。
  3. 递归展开过程：像“连锁反应”一样，会一直把 i 所在连通分量里的所有城市都访问完。

这样说还是有点复杂，举个例子说明：

假设 isConnected = [[1,1,0],[1,1,0],[0,0,1]]：

  • 城市 0 → 连着城市 1
  • 城市 2 自成一组

执行过程：

  1. j=0：未访问 → DFS(0)，递归会顺带访问 1 → ans=1
  2. j=1：已访问，跳过
  3. j=2：未访问 → DFS(2)，只访问自己 → ans=2

最终答案：2 个省份

反思

  1. 这道题还可以用并查集，并查集是一种数据结构，三个字分别代表不同的意思：合并、查找、集合
  2. 这题本质是连通分量计数，dfs 函数的递归作用：把从某个起点出发能到达的所有节点“一网打尽”，每次外层循环找到一个未访问城市，就意味着发现一个新省份

结果

时间复杂度：$O(N^2)$

空间复杂度：$O(N)$

已是最优解