朋友圈（省份数量）
这题本质上就是在数无向图的连通分量，矩阵只是输入形式，不要被题面里的“省份”两个字带偏。
问题描述
LeetCode 547 - 省份数量
有n个城市，给定一个n×n的矩阵isConnected，其中isConnected[i][j] = 1表示城市i和城市j直接相连，否则为0。计算省份的数量（连通分量数量）。
输入: isConnected = [
[1,1,0],
[1,1,0],
[0,0,1]
]
输出: 2
说明: 城市0和1相连为一个省份，城市2单独为一个省份
解题思路
- 连通分量：统计图中连通分量的数量
- DFS/BFS：从每个未访问城市开始DFS/BFS
- 并查集：使用并查集合并相连的城市
- 邻接矩阵：直接使用给定的邻接矩阵
为什么每启动一次 DFS，答案就加一
因为一次 DFS 会把某个城市所在的整个连通块全部访问掉。
所以外层枚举到一个还没访问过的城市时，就说明我们发现了一个新的省份。
Go 代码
Go 实现
func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
visited := make([]bool, n)
count := 0
var dfs func(int)
dfs = func(city int) {
visited[city] = true
for neighbor := 0; neighbor < n; neighbor++ {
if isConnected[city][neighbor] == 1 && !visited[neighbor] {
dfs(neighbor)
}
}
}
for city := 0; city < n; city++ {
if !visited[city] {
count++
dfs(city)
}
}
return count
}易错点
这题代码不难，容易错在建模心态上。
- 这是无向图，邻接矩阵理论上是对称的。
isConnected[i][i] == 1不代表要特殊处理，它只是自连通。- 用 DFS / BFS / 并查集都能做，别在实现前摇摆三套思路。
- 邻接矩阵输入下，时间复杂度天然就是
O(n^2)量级。
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| DFS/BFS | O(N²) | O(N) |
| 并查集 | O(N² α(N)) | O(N) |