LC547 · 省份数量
Number of Provinces
给你一张城市连接表，问一共有几个互不相连的城市群。
中文原题说明
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内任意城市都能通过若干连接到达；不同省份之间没有连接。
给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，isConnected[i][j] = 0 表示不直接相连。
返回矩阵中省份的数量。
isConnected = [ [1,1,0], [1,1,0], [0,0,1] ]
输出：2
解释：城市 0 和 1 是一个省份，城市 2 是另一个省份。
先把问题说成人话
这题不是问有多少条边，而是问有多少个互不相连的城市群。
只要两个城市能通过一串连接到达，就属于同一个省份；不要求它们必须直接相连。
示例里 0 和 1 直接相连，所以它们是一组；2 没有和别人相连，所以自己是一组。
矩阵里的 1 就是一条边
同一个示例会贯穿 DFS 和并查集：矩阵里的 [0][1] = 1 会在城市图中变成 0 - 1 这条边，最后得到两个连通分量：{0,1} 和 {2}。
动画实验台
DFS Step 1：初始化
初始化：visited = [false,false,false], ans = 0。visited 记录哪些城市已经被某个省份收走，ans 记录已经找到几个省份。
高亮当前读取的行或格子
同一个示例的 3 个城市
初始化：visited = [false,false,false], ans = 0。visited 记录哪些城市已经被某个省份收走，ans 记录已经找到几个省份。
DFS Go / 并查集 Go
func findCircleNumDFS(isConnected [][]int) int {
n := len(isConnected)
visited := make([]bool, n) // visited[i] 表示城市 i 是否已经被某个省份访问过
var dfs func(int)
dfs = func(city int) {
visited[city] = true // 进入城市 city，就把它标记为已访问
for j := 0; j < n; j++ {
// 有边，并且对方城市还没访问过，才继续向外走
if isConnected[city][j] == 1 && !visited[j] {
dfs(j)
}
}
}
ans := 0
for i := 0; i < n; i++ {
if !visited[i] { // 找到一个还没归属的城市，说明发现新省份
ans++
dfs(i)
}
}
return ans
}DFS 初始化
这一段在干什么：建立 visited 数组。它不是答案，只是防止同一个城市被反复访问。
dfs(city)
这一段在干什么：从 city 出发，沿着矩阵里值为 1 的边，把能到达的城市全部标成 visited。
主循环 ans++
这一段在干什么：每遇到一个还没访问过的城市，就说明发现一个新的连通分量，所以 ans++ 并启动一次 DFS。
同一件事，两种视角
DFS
DFS：像走地图，从一个城市出发，把能到达的城市都访问掉。
并查集
并查集：像合并组织，看到两个城市相连，就把两个集合合并。
面试里按这个顺序讲
- 1.先把题目翻译成图：城市是点，矩阵里的 1 是边，答案是连通分量个数。
- 2.DFS 写法更直观：主循环遇到未访问城市就 ans++，然后 DFS 把整个省份标记掉。
- 3.并查集写法更模板化：count 初始为 n，每次 union 两个不同 root 时 count--。
- 4.复杂度都要从矩阵扫描看起：无论用哪种方法，都需要检查 O(n²) 个格子。