LC547. 省份数量

题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。

示例 1： MItwbXxSToays9xEQwqc49p5nud.jpg

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

输出： 2 示例 2： SRVNb8WyqoZbTEx96VLc6aYpnfc.jpg

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

输出： 3

题目解析

好的，没问题！我是 AlgoMooc 的算法老师。我们不讲那些让人头晕的术语，就用大白话，像聊天一样，把这道题给你讲明白。

---

题目在说什么

想象一下，你有一张中国地图，上面标着很多城市。有些城市之间直接通了高铁（isConnected[i][j] = 1），有些没有（isConnected[i][j] = 0）。

现在，题目定义了一个“省份”的概念：只要两个城市能通过高铁网络（不管是直达还是中转）连在一起，它们就属于同一个省份。

比如：

• 北京和天津直达，天津和上海直达，那么北京、天津、上海就是一个省份。
• 广州和深圳直达，但和北京那边没有高铁相连，那广州、深圳就是另一个省份。

题目给你的，就是一张 “城市之间有没有直达高铁” 的表格（矩阵 isConnected）。表格的行和列都代表城市编号（0, 1, 2...）。如果 isConnected[i][j] = 1，就表示城市 i 和城市 j 有直达高铁。

你的任务就是：数一数，这张地图上一共有多少个“省份”？

---

思路是怎么来的

这个问题，本质上就是在一个“朋友圈”里，数一数有多少个“小圈子”。

生活化的比喻： 假设你有一堆朋友，你想知道他们分成了几个互相不认识的小团体。你会怎么做？

1. 随便拉一个人（比如小明），让他当“起点”。 2. 问小明：“你的朋友都有谁？” 小明会告诉你小红、小刚。 3. 再问小红：“你的朋友都有谁？” 小红可能会告诉你小刚、小丽。 4. 一直问下去，直到把所有能被小明“间接认识”的人都找出来。这些人，就是一个“小团体”。 5. 然后，从剩下没被问到的人里，再随便拉一个，重复上面的步骤。 6. 每完成一次“追问到底”的过程，就找到了一个小团体。最后数一数，就知道有几个小团体了。

在这个题目里，“城市”就是你的“朋友”，“直达高铁”就是“直接认识”，“省份”就是“小团体”。

核心思想就是： 从一个没被“拜访”过的城市开始，沿着高铁线路，把能到达的所有城市都“拜访”一遍，并标记为“已拜访”。每完成一次这样的“地毯式搜索”，就找到了一个省份。然后，继续寻找下一个没被“拜访”过的城市，重复这个过程。

---

代码逐步拆解

我们以 DFS（深度优先搜索） 的代码为例来拆解。DFS 就像“一条路走到黑，撞了南墙再回头”。

第一步：准备工作

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;  // 1. 城市的总数
    int ans = 0;                 // 2. 省份计数器，初始为0
    int[] checkList = new int[n]; // 3. 拜访记录本，长度为n，初始全是0
    // ... 遍历每个城市
}

• `n`：就是城市的总个数，比如有3个城市，n就是3。
• `ans`：就是我们最后要输出的答案，目前还没找到任何省份，所以是0。
• `checkList`：这是一个长度为 n 的数组，就像一个“拜访记录本”。checkList[i] = 0 表示城市 i 还没被拜访过；checkList[i] = 1 表示已经拜访过了。一开始，所有城市都没被拜访，所以全是0。

第二步：开始“地毯式搜索”

for (int i = 0; i < n; i++) {
    if (checkList[i] == 0) {   // 4. 如果城市i没被拜访过
        dfs(isConnected, checkList, i); // 5. 从i开始，进行深度优先搜索
        ans++;                  // 6. 搜索完一个完整的“省份”，计数器+1
    }
}
return ans;

• 第4行：我们从头到尾检查每个城市。如果发现某个城市 i 的拜访记录是“0”（没去过），说明它属于一个我们还没发现的省份。
• 第5行：好，发现新大陆了！我们立刻派出一队探险队（dfs函数），从城市 i 出发，沿着所有高铁线路，把能到的所有城市都逛一遍，并在“拜访记录本”上标记为“1”。
• 第6行：探险队回来了，意味着这个省份里所有的城市都找齐了。所以，省份数量 ans 增加1。

第三步：DFS 探险队是怎么工作的？

private void dfs(int[][] isConnected, int[] checkList, int i) {
    checkList[i] = 1;  // 7. 到达城市i，先在本子上记下“已拜访”
    for (int j = 0; j < isConnected.length; j++) { // 8. 查看城市i的高铁线路图
        if (checkList[j] == 0 && isConnected[i][j] == 1 && i != j) {
            // 9. 如果城市j没去过，并且从i有直达高铁到j，并且j不是i自己