LC547Medium图DFS连通分量邻接矩阵

省份数量

题目给的是数字矩阵，真正要数的是城市图里互不连通的群组。每从一个未访问城市启动一次 DFS，就完整发现一个新省份。

题目是什么

根据城市连接矩阵，统计直接或间接相连的城市群数量。

解决什么问题

把邻接矩阵建模成无向图，并计算图的连通分量。

核心结论

扫描所有城市；遇到未访问城市就答案加一，再用 DFS 标记它所在的整个分量。

01交互算法精讲

先说结论：这道题到底解决什么

题目给的是一张充满 0 和 1 的矩阵，怎样把它翻译成城市连通关系，并证明每次从未访问城市启动 DFS 就恰好发现一个新省份？

中心结论：扫描所有城市；遇到未访问城市就答案加一，再用 DFS 标记它所在的整个分量。

读完必须能回答

1.为什么矩阵中的 1 的数量不等于省份数量？
2.为什么一次 DFS 可以完整覆盖一个省份，却不会越界到另一个省份？
3.为什么答案应该在启动 DFS 时增加，而不是每访问一个城市时增加？

02交互算法精讲

完整题目与题意拆解

有 n 个城市，isConnected 是 n×n 邻接矩阵。若 isConnected[i][j]=1，城市 i 与 j 直接相连。

直接或间接相连的一组城市构成一个省份。返回矩阵中省份的总数量。

• 连接关系可通过中间城市间接传递。
• 矩阵对称，且对角线 isConnected[i][i] 为 1。
• 省份数量不是矩阵中 1 的数量。

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
解释：城市 0、1 属于同一省份，城市 2 单独形成另一个省份。

把每个城市看作图中的点，把矩阵里的非对角 1 看作无向边。问题立刻变成：这张图有几个连通分量。

一次从城市 i 出发的 DFS 会沿所有连接走到同一个省份内的每个城市。之后外层循环再遇到这些城市时，它们已经访问，不应重复计数。

答案增加的时机是“发现一个未访问的起点”，不是“访问一个城市”或“看到一条边”。

动画 1 · 题意扫描

把数字表翻译成城市地图

观察矩阵中的 1 怎样变成图上的边，以及间接连接为什么也属于同一省份。

Step 1/20%

矩阵 → 无向图

城市 0

城市 1

城市 2

省份 = 连通分量

先把矩阵翻译成城市图

发生了什么: 矩阵中的 isConnected[0][1]=1 变成边 0—1，城市 2 没有通往其他城市的边。
为什么: 省份描述的是可达关系，图的连通分量正好表达直接与间接连接。
下一步: 准备 visited 和省份计数器。

当前状态

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：矩阵只是图的输入形式；题目真正要数的是连通分量。

03交互算法精讲

第一层方案：暴力做法

可以为每个城市维护集合，并反复扫描矩阵，把有连接的集合合并，直到没有变化。这会重复检查同样的边和集合。

也可以从每个城市单独做可达性搜索，再比较可达集合，但同一个省份会被多次完整遍历。

for each city i:
  从 i 重新搜索所有可达城市
  再判断这个集合是否已出现

visited 让一个省份只被完整遍历一次；外层只需跳过已经染色的城市。

动画 2 · 暴力重复

为什么不能数 1，也不能按访问城市计数

对照矩阵、visited 和第一次 DFS，观察同一条无向边会重复出现，同一省份也含多个城市。

Step 1/30%

矩阵 → 无向图

城市 0

城市 1

城市 2

省份 = 连通分量

先把矩阵翻译成城市图

发生了什么: 矩阵中的 isConnected[0][1]=1 变成边 0—1，城市 2 没有通往其他城市的边。
为什么: 省份描述的是可达关系，图的连通分量正好表达直接与间接连接。
下一步: 准备 visited 和省份计数器。

当前状态

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：边数、节点数和连通分量数是三个不同量，答案只统计新分量。

优化方向：邻接矩阵已经给出从任一城市到所有候选邻居的连接信息。DFS 扫描一行即可找到下一批城市。

04交互算法精讲

整体地图：先做什么，再做什么

先完成建模：城市是图节点，`isConnected[i][j]==1` 表示 i、j 之间有直接边；直接或间接可达的一整组城市就是一个连通分量，也就是一个省份。

再用 visited 记录已归属某个分量的城市。外层逐个扫描城市，只有遇到未访问城市才把 provinces 加一，并启动 DFS 把该分量中的所有城市标记。

• 矩阵负责描述边，不直接描述省份编号。
• DFS 负责从一个起点覆盖整个连通分量。
• 外层未访问判断负责发现下一个分量。

算法有两层职责：内层 DFS 回答“这一省有哪些城市”，外层循环回答“一共有多少省”。

05交互算法精讲

邻接矩阵、图和连通分量是什么关系

矩阵第 i 行描述城市 i 与哪些城市直接相连。连接具有传递性：即使 0 与 2 没有直接边，只要存在 0—1—2 的路径，它们仍属于同一个省份。

因此不能数矩阵中的 1。对角线上的 1 只是城市连接自己，无向边又会在矩阵中对称出现两次；省份数量取决于有多少互相不可达的城市组。

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

图：0 — 1    2
连通分量：{0,1}、{2}
答案：2

一次 DFS 涂满的是“从起点可达的全部节点”，这正好就是连通分量的定义。

动画 3 · 核心概念

一次 DFS 把一个连通分量完整涂色

从城市 0 出发，观察直接连接和访问标记怎样把 {0,1} 变成一组。

Step 1/40%

发现新分量

城市 0

城市 1

城市 2

provinces: 0 → 1

城市 0 未访问，发现第一个省份

发生了什么: 外层指针到 city=0，provinces 从 0 增加到 1，并启动 dfs(0)。
为什么: 如果此前搜索能到达 0，它早已被标记；未访问意味着这是一个新分量入口。
下一步: 进入 DFS 后立即标记城市 0。

当前状态

city

provinces

0→1

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：从一个起点能到达的全部城市，正好构成它所在的省份。

06交互算法精讲

如何用 DFS 启动次数计数

DFS 一进入 city 就立即 `visited[city]=true`，再扫描矩阵该行。只有 connected==1 且 next 未访问时递归，这会沿直接边不断扩展到全部间接可达城市。

外层扫描遇到已访问城市时直接跳过；遇到未访问城市说明此前所有 DFS 都无法到达它，因此它必然属于一个尚未计数的新省份。

• 先计数再 DFS，表示发现一个新分量并立即覆盖它。
• 进入 DFS 立即标记，防止无向边把调用带回上一节点。
• 外层最终扫描所有城市，保证没有分量遗漏。

定义递归闭包 dfs(city)，先 `visited[city]=true`，再遍历 isConnected[city] 的每一列。

主循环遇到未访问城市时先计数，再调用 dfs。全部城市扫描完成后返回 provinces。

并查集也能解决本题：扫描连接并 union，最后统计根。但静态邻接矩阵求连通分量时，DFS 的建模与代码更直接。

动画 4 · 机制构建

未访问起点计数，已访问城市跳过

逐步观察 provinces 何时增加、visited 何时写入，以及为什么城市 1 不会重复计数。

Step 1/60%

初始化

城市 0

城市 1

城市 2

visited=[F,F,F] · provinces=0

所有城市一开始都未访问

发生了什么: 创建 visited=[false,false,false]，provinces=0。
为什么: visited 记录哪些城市已经被某次省份搜索覆盖。
下一步: 外层循环从城市 0 开始。

当前状态

visited

[F,F,F]

provinces

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：计数发生在覆盖新分量之前，而不是 DFS 每访问一个节点时。

07交互算法精讲

核心难点：为什么 DFS 启动次数等于省份数

每次从未访问城市 s 启动 DFS 时，s 不在此前任何已覆盖分量中，因此这次启动至少对应一个新省份。DFS 只沿矩阵值为 1 的边移动，不可能跨到与 s 不连通的其他省份。

同时，DFS 会沿所有直接边递归，最终到达与 s 间接连通的每个城市，所以同一省份不会在后续再次产生未访问起点。

由此每个省份恰好触发一次 DFS：不会少，因为外层检查所有城市；不会多，因为第一次 DFS 已把整个省份标记。

这是一个一一对应证明：新 DFS 启动 ↔ 尚未覆盖的连通分量。

正确性抓手

• 每次从未访问城市启动 DFS 时，它不属于此前任何分量，因此答案应增加一。
• DFS 会且只会标记与起点连通的全部城市，不会跨越值为 0 的非连接。
• 外层最终检查所有城市，所以每个连通分量恰好被计数一次。

08交互算法精讲

完整执行过程

观察 provinces 只在启动新 DFS 时增加：城市 0 的 DFS 一次覆盖 0、1；城市 1 被跳过；孤立城市 2 启动第二次 DFS。

1把主例矩阵翻译成城市图：0 与 1 相连，2 是孤立城市。
2visited 初始全为 false；外层遇到城市 0 未访问，provinces 从 0 变 1。
3DFS 标记 0，并沿矩阵中的连接访问 1；{0,1} 整组被覆盖。
4外层扫描城市 1 时发现已访问，不重复计数。
5城市 2 仍未访问，启动第二次 DFS 并令 provinces=2；全部城市处理后返回 2。

动画 5 · 完整执行

完整得到 {0,1} 与 {2} 两个省份

播放矩阵建模、第一次 DFS 覆盖、跳过已访问城市和第二次 DFS。

Step 1/90%

矩阵 → 无向图

城市 0

城市 1

城市 2

省份 = 连通分量

先把矩阵翻译成城市图

发生了什么: 矩阵中的 isConnected[0][1]=1 变成边 0—1，城市 2 没有通往其他城市的边。
为什么: 省份描述的是可达关系，图的连通分量正好表达直接与间接连接。
下一步: 准备 visited 和省份计数器。

当前状态

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：外层启动了两次覆盖搜索，所以恰好存在两个连通分量。

09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立，再看对应代码，而不是先背模板。

动画 6 · 代码映射

内层涂色与外层计数逐行对应

观察 DFS 的标记和邻居递归，以及外层未访问判断、provinces++、最终返回。

Step 1/60%

发现新分量

城市 0

城市 1

城市 2

provinces: 0 → 1

城市 0 未访问，发现第一个省份

发生了什么: 外层指针到 city=0，provinces 从 0 增加到 1，并启动 dfs(0)。
为什么: 如果此前搜索能到达 0，它早已被标记；未访问意味着这是一个新分量入口。
下一步: 进入 DFS 后立即标记城市 0。

当前状态

city

provinces

0→1

当前 Go 代码

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

看完带走：内层不修改答案，外层只在发现未覆盖分量时修改答案。

Step 1

先把矩阵翻译成城市图

省份描述的是可达关系，图的连通分量正好表达直接与间接连接。

func · n

Step 2

所有城市一开始都未访问

visited 记录哪些城市已经被某次省份搜索覆盖。

visited-init · provinces-init · outer-loop

Step 3

城市 0 未访问，发现第一个省份

如果此前搜索能到达 0，它早已被标记；未访问意味着这是一个新分量入口。

outer-if · provinces-plus · call-dfs

Step 4

DFS 进入城市 0 就立即标记

无向图存在返回边，先标记能阻止搜索从 1 又递归回 0。

dfs-def · mark-visited · scan-row

Step 5

沿连接边访问城市 1

0 与 1 直接相连，它们必须被同一次 DFS 染成同一个省份。

scan-row · neighbor-if · dfs-next · mark-visited

Step 6

0、1 的搜索结束，第一个省份完整

一次 DFS 已穷尽从 0 可达的所有城市，因此这个连通分量不会再被重复搜索。

neighbor-if · outer-loop

Step 7

城市 1 已访问，不能重复计数

它已属于从城市 0 发现的同一个连通分量。

outer-loop · outer-if

Step 8

孤立城市 2 形成第二个省份

城市 2 无法从 {0,1} 到达，是一个独立连通分量。

outer-if · provinces-plus · call-dfs · mark-visited

Step 9

启动两次 DFS，答案就是 2

邻接矩阵的每一行最多扫描一次，总共检查 n² 个位置；visited 与递归栈最多 n。

return-answer · scan-row

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

1func findCircleNum(isConnected [][]int) int {2    n := len(isConnected)3    visited := make([]bool, n)4    var dfs func(int)5    dfs = func(city int) {6        visited[city] = true7        for next, connected := range isConnected[city] {8            if connected == 1 && !visited[next] {9                dfs(next)10            }11        }12    }13    provinces := 014    for city := 0; city < n; city++ {15        if !visited[city] {16            provinces++17            dfs(city)18        }19    }20    return provinces21}

最小测试集合

// 两个省份
findCircleNum([][]int{{1,1,0},{1,1,0},{0,0,1}}) // 2

// 全部城市直接或间接连通
findCircleNum([][]int{{1,1,0},{1,1,1},{0,1,1}}) // 1

// 所有城市互相孤立
findCircleNum([][]int{{1,0,0},{0,1,0},{0,0,1}}) // 3

// 单城市本身就是一个省份
findCircleNum([][]int{{1}}) // 1

11交互算法精讲

正确性与复杂度

时间复杂度 O(n²)

每个城市只进入 DFS 一次，但邻接矩阵的每一行都要扫描 n 个连接位置。

空间复杂度 O(n)

visited 数组占 O(n)，递归栈在一个大连通分量中最坏也为 O(n)。

12交互算法精讲

最容易写错的地方

错误 1

统计矩阵中 1 的数量，而不是连通分量。

错误 2

每访问一个城市都 provinces++，导致同一省份重复计数。

错误 3

进入 DFS 后没有立即标记，沿无向边无限来回。

错误 4

把矩阵对称误解为时间可以低于 O(n²)，却仍扫描了完整矩阵。

13交互算法精讲

最后复盘：带走逻辑链

1.矩阵是输入形式，图和连通分量才是问题本质。
2.未访问起点代表新省份，一次 DFS 覆盖整个省份。
3.答案等于覆盖搜索的启动次数。
4.迁移题：LC200 岛屿数量、LC684 并查集判环。

面试表达

1.把邻接矩阵建模成无向图，省份就是连通分量。
2.维护 visited，扫描每个城市；遇到未访问城市就 provinces++ 并启动 DFS。
3.DFS 扫描该城市所在矩阵行，把所有相连且未访问城市递归标记。
4.矩阵总共检查 O(n²) 个位置，visited 和递归栈空间 O(n)。