第8章｜图与并查集
Unit 10 · LeetCode #547 省份数量
仅本次页面有效
U10
Connected Components · DSUMatrix → Find Roots → Union Sets → Count Components
省份不是“直接相连的边数”，
而是传递连通后的集合数量。
同一张城市关系图既可以通过 DFS/BFS 逐个搜索连通分量，也可以通过并查集不断合并集合。本单元作为章节转折点：先用熟悉的遍历理解“省份”，再把这个语义压缩到 parent / size / components 三组状态中。
检测到上次学习现场阶段、案例、矩阵扫描、父指针、代码槽位与迁移进度都可恢复。
LeetCode #547 · 省份数量
有 n 个城市。若城市可以直接或间接互相到达，它们属于同一个省份。给定 n × n 矩阵 isConnected，其中 isConnected[i][j] == 1 表示城市 i 与城市 j 直接相连。返回省份总数。
示例 1
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
约束与 Python 签名
1 ≤ n ≤ 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] ∈ {0, 1}
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
class Solution:
def findCircleNum(self, isConnected):
...
矩阵关于主对角线对称，因此扫描无向边时只需考虑 i < j 的上三角区域。
Connected Component
任意两点可通过路径互达、且无法再加入外部节点的一组节点。
Representative / Root
并查集中一个集合的代表节点；两个城市根相同，表示已经连通。
Path Compression
find 返回根的同时缩短父指针路径，让后续查询更快。
Union by Size
把较小集合的根挂到较大集合的根下，避免父指针树过深。
矩阵与城市图步骤 1