尧图网站开发 
LeetCode 547 省份数量题解并查集、DFS、BFS 三种连通分量计数方案【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 LeetCode 547「省份数量」旧题名「朋友圈」为核心讲解如何把N x N邻接矩阵建模为无向图并通过并查集Union-Find、DFS、BFS 三种经典算法统计图中的连通分量个数。文章以仓库中的题解文档为主体结合并查集专题讲解覆盖 Python、Java、C 三种语言的实现帮助你掌握“连通性”一类问题的通用套路。题目背景与题意有 N 个城市其中一些彼此相连另一些没有相连。如果城市 A 与城市 B 直接相连且城市 B 与城市 C 直接相连那么城市 A 与城市 C间接相连。省份是一组直接或间接相连的城市组内不含其他没有相连的城市。题目给定一个N x N的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连isConnected[i][j] 0表示二者不直接相连要求返回矩阵中省份的数量。示例 1输入: [[1,1,0], [1,1,0], [0,0,1]] 输出: 2 说明已知城市 0 和城市 1 相连他们在一个省份。 第 2 个城市自己在一个省份。所以返回 2。示例 2输入: [[1,1,0], [1,1,1], [0,1,1]] 输出: 1 说明已知城市 0 和城市 1 直接相连城市 1 和城市 2 直接相连所以城市 0 和城市 2 间接相连所以他们三个在一个省份返回 1。注意N 在[1, 200]的范围内对于所有城市有M[i][i] 1每个城市与自身连通如果有M[i][j] 1则有M[j][i] 1邻接矩阵对称图为无向图。建模邻接矩阵 → 无向图 → 连通分量题目的关键一步是把给定矩阵看作图的邻接矩阵Adjacency Matrix矩阵的每个下标对应图中的一个顶点城市M[i][j] 1对应一条无向边(i, j)。这样问题就转化为求一个无向图中连通分量的个数英文版题解文档 547.friend-circles-en.md 中明确指出了这一转化思路。连通分量问题通常可以用DFS、BFS、并查集Union-Find三种方式解决。下面逐一展开。方法一并查集Union-Find思路并查集有一个功能是轻松计算连通分量而本题省份的个数本质上就是连通分量的个数因此用并查集可以完美解决见主文档 547.number-of-provinces.md 的思路小节。做法很简单初始时每个城市自成一个省份cnt记为N遍历邻接矩阵只需遍历i j的下三角即可因为矩阵对称遇到M[i][j] 1就将i与j所在的集合合并每成功合并一次cnt减 1。遍历结束后cnt就是省份连通分量的数量。Python 实现主文档给出的代码将并查集模板单独抽出find、union、connected都是典型模板方法class UF: parent {} cnt 0 def __init__(self, M): n len(M) for i in range(n): self.parent[i] i self.cnt 1 def find(self, x): while x ! self.parent[x]: x self.parent[x] return x def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] self.find(q) self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def findCircleNum(self, M: List[List[int]]) - int: n len(M) uf UF(M) for i in range(n): for j in range(i): if M[i][j] 1: uf.union(i, j) return uf.cnt复杂度分析时间复杂度平均O(logN)最坏的情况是O(N)。原因在于主文档的find实现没有做路径压缩当树退化成链时find、union、connected都会退化到O(N)空间复杂度使用了parent数组为O(N)。优化方向按大小合并 路径压缩主文档明确指出两条优化路径按大小按秩合并为每一个顶层元素维护一个size表示其连通分量的大小union时总是将小树拼接到大树上。这样可以避免树不断长高将树高控制在O(logN)级别路径压缩在find过程中将沿途节点直接挂到根节点上把树高压缩到常数级别配合按秩合并后find/union的均摊时间复杂度可以趋近O(1)。仓库的并查集专题文档 union-find.md 给出了同时包含路径压缩与按大小合并的完整模板class UF: def __init__(self, M): self.parent {} self.size {} self.cnt 0 # 初始化 parentsize 和 cnt # size 是一个哈希表记录每一个联通域的大小其中 key 是联通域的根value 是联通域的大小 # cnt 是整数表示一共有多少个联通域 for i in range(M): self.parent[i] i self.cnt 1 self.size[i] 1 def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上 使树尽量平衡 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_q] self.size[leader_p] else: self.parent[leader_q] leader_p self.size[leader_p] self.size[leader_q] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q)关于路径压缩的意义专题文档中有一个直观解释每次find都会从当前节点向上不断搜索直到根节点因此find的时间复杂度大致等于节点的深度如果不加控制树高可能等于节点数find会退化到O(N)。而路径压缩后树的平均高度不超过logN如果同时使用路径压缩与按秩合并时间复杂度趋近O(1)——更严谨的说法是“阿克曼函数的某个反函数”即近乎常数的均摊复杂度。下面是并查集解法在处理示例输入时的完整流程示意图图中展示了union(0,1)、union(0,2)、union(1,3)逐步合并的过程初始count 5每成功合并一次count减 1最终得到两个连通分量{0,1,2,3}与{4}因此省份数为 2。C 实现每日一题存档仓库的每日一题存档 daily/2019-08-11.md 给出了带路径压缩的 C 版本其核心思想完全一致可作为多语言对照class Solution { public: int findCircleNum(vectorvectorint M) { if (M.empty()) return 0; vectorint pre(M.size()); for(int i0; iM.size(); i) pre[i] i;//先各自为组组名也为自己的序号 int group M.size();//一开始有多少人就有多少个朋友圈当每出现一对朋友时就减1最后就是总的朋友圈数量了。 for(int i0; iM.size(); i) { for(int j0; jM.size(); j) { if (i ! j M[i][j] 1) { int x1 find(i, pre);//x1为i所属的组 int x2 find(j, pre);//x2为j所属的组 if (x1 ! x2) { //如果不属于同个朋友圈的话就把i归为j的组 pre[x1] x2; group--; } } } } return group; } private: int find(int x, vectorint pre) { //“pre[x] ”这句为路径压缩直接指向组的根节点下次查询时就快很多了。 return pre[x]x ? x : pre[x] find(pre[x], pre); } };这段代码中pre[x] find(pre[x], pre)的递归写法就是路径压缩让当前节点直接指向组的根节点下次查询时就能以O(1)的代价找到根。方法二DFS思路DFS 思路详见英文版文档 547.friend-circles-en.md从每个节点出发做 DFS用visited数组标记已访问节点每次 DFS 都会访问当前节点所有直接相连的节点在邻接矩阵的当前行中扫描M[i][j] 1且未访问的j一次完整的 DFS 恰好覆盖一个连通分量因此启动 DFS 的次数就是连通分量省份的个数。复杂度分析时间复杂度O(N * N)其中 N 是城市数量需要遍历整个N x N矩阵空间复杂度O(N)visited数组大小为 N。Java 实现class FindCirclesDFS { public int findCircleNumDFS(int[][] M) { if (M null || M.length 0 || M[0].length 0) return 0; int n M.length; int numCircles 0; boolean[] visited new boolean[n]; for (int i 0; i n; i) { if (!visited[i]) { dfs(M, i, visited, n); numCircles; } } return numCircles; } private void dfs(int[][] M, int i, boolean[] visited, int n) { for (int j 0; j n; j) { if (M[i][j] 1 !visited[j]) { visited[j] true; dfs(M, j, visited, n); } } } }每日一题存档的 DFS 变体daily/2019-08-11.md 还给出了一种用整型visited数组实现的等价写法便于对比public class Solution { public void dfs(int[][] M, int[] visited, int i) { for (int j 0; j M.length; j) { if (M[i][j] 1 visited[j] 0) { visited[j] 1; dfs(M, visited, j); } } } public int findCircleNum(int[][] M) { int[] visited new int[M.length]; int count 0; for (int i 0; i M.length; i) { if (visited[i] 0) { dfs(M, visited, i); count; } } return count; } }DFS 的遍历过程如下图所示从节点 0 出发依次访问 1、3、2同一连通分量内的节点在一次 DFS 中全部被标记之后从未访问的节点 4 再启动第二次 DFS方法三BFS层级遍历思路BFS 的思路同样详见英文版文档 547.friend-circles-en.md从一个节点出发访问其所有直接相连的节点即访问同一层级的全部节点使用visited数组标记已访问节点用队列保存待扩展节点每当从一个新的未访问节点启动 BFS 时计数加 1该次 BFS 覆盖的正是同一个连通分量。复杂度分析时间复杂度O(N * N)遍历整个矩阵空间复杂度O(N)队列与visited数组大小均为 N。Java 实现class FindCircleBFS { public int findCircleNumBFS(int[][] M) { if (M null || M.length 0) return 0; int numCircle 0; int n M.length; boolean[] visited new boolean[n]; QueueInteger queue new LinkedList(); for (int i 0; i n; i) { // already visited, skip if (visited[i]) continue; queue.add(i); while (!queue.isEmpty()) { int curr queue.poll(); visited[curr] true; for (int j 0; j n; j) { if (M[curr][j] 1 !visited[j]) { queue.add(j); } } } numCircle; } return numCircle; } }BFS 按层级扩散的过程如下图所示第 0 层只有节点 0第 1 层是 1 和 2第 2 层是 3节点 4 单独成连通分量三种方法对比与选择方法核心思想时间复杂度空间复杂度特点并查集合并相邻节点统计集合个数平均O(logN)最坏O(N)路径压缩 按秩合并后趋近O(1)O(N)parent 数组模板化程度高可扩展性强带权并查集、离线查询适合“多次动态询问连通性”的场景DFS一次 DFS 覆盖一个连通分量O(N * N)O(N)visited 数组实现最简单直观天然递归BFS一次 BFS 覆盖一个连通分量O(N * N)O(N)队列 visited层级遍历可顺便求最短路径等额外信息从源码结构看并查集是主文档problems/547.number-of-provinces.md与并查集专题thinkings/union-find.md共同推崇的解法原因在于并查集只回答“联通与否”而不关心“具体联通路径”其三个核心 APIfind/union/connected可以像模板一样套用在大量连通性问题中。并查集核心原理速览三个核心 APIfind(x)不断沿parent向上查找找到 x 所属集合的根代表元素。根满足parent[x] xconnected(p, q)判断find(p) find(q)若祖先相同则两点连通union(p, q)将其中一个节点挂到另一个节点的祖先上使两者祖先相同从而联通。parent[x] y表示 x 的父节点是 y。之所以用 parent 存储父节点而非用 children 存储子节点是因为并查集的核心需求是“找到某个元素的代表根”见 union-find.md 的形象解释小节。两个关键优化路径压缩find递归时将沿途节点的parent直接指向根把树高压缩到常数级别降低后续查找代价按秩按大小合并union时把小的树挂到大的树上避免树不断增高使树保持平衡。专题文档中的复杂度结论令 n 为图中点的个数空间复杂度为O(n)parent带权并查集还有 weight时间上路径压缩 按秩合并优化后union和find的均摊复杂度接近于O(1)更严谨的表达是O(log(m × Alpha(n)))其中 Alpha 是阿克曼函数的某个反函数若只做路径压缩或只做按秩合并则复杂度分别为O(logx)和O(logy)x、y 分别为合并与查找的次数。经典应用检测图是否有环并查集除了统计连通分量还常用来检测无向图中是否存在环只需对每条边先判断connected(a, b)若合并之前已经联通说明存在环见 union-find.md 的应用小节uf UF() for a, b in edges: if uf.connected(a, b): return False uf.union(a, b) return True此外并查集还是最小生成树经典算法 Kruskal 的基础。相关题目与拓展并查集专题文档 union-find.md 在“练习”一节推荐了一系列连通性问题与本题目547属于同一套路建议练手账户合并无权图连通性模板题等式方程的可满足性无权图连通性交换字符串中的元素无权图连通性检查边长度限制的路径是否存在带权图连通性上面的题目中前四道都是无权图的连通性问题第五道是带权图的连通性问题。判断一道题是否适用并查集核心信号是题目中出现连通、等价这类关系描述。总结LeetCode 547「省份数量」是一道非常典型的“连通分量计数”题目题目给出的N x N矩阵本质上就是图的邻接矩阵于是问题被规约为求无向图连通分量个数并查集是主文档首推的解法初始每个城市自成一省遍历矩阵下三角对M[i][j] 1执行union每成功合并一次计数减 1最终计数即省份数量。注意find若不压缩最坏会退化到O(N)通过按大小合并 路径压缩可将均摊复杂度降到趋近O(1)DFS / BFS通过visited数组标记访问一次遍历恰好覆盖一个连通分量启动遍历的次数即省份数时间复杂度为O(N²)空间复杂度O(N)。掌握本题的价值在于吃透“连通性”这一类问题的通用模板之后遇到 721 账户合并、990 等式方程的可满足性、1697 带权连通性等题目都可以直接套用并查集模板快速求解。更完整的并查集原理、带权并查集模板与练习清单可继续阅读仓库中的 并查集专题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
LeetCode 547 省份数量题解并查集、DFS、BFS 三种连通分量计数方案【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文以 LeetCode 547「省份数量」旧题名「朋友圈」为核心讲解如何把N x N邻接矩阵建模为无向图并通过并查集Union-Find、DFS、BFS 三种经典算法统计图中的连通分量个数。文章以仓库中的题解文档为主体结合并查集专题讲解覆盖 Python、Java、C 三种语言的实现帮助你掌握“连通性”一类问题的通用套路。题目背景与题意有 N 个城市其中一些彼此相连另一些没有相连。如果城市 A 与城市 B 直接相连且城市 B 与城市 C 直接相连那么城市 A 与城市 C间接相连。省份是一组直接或间接相连的城市组内不含其他没有相连的城市。题目给定一个N x N的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连isConnected[i][j] 0表示二者不直接相连要求返回矩阵中省份的数量。示例 1输入: [[1,1,0], [1,1,0], [0,0,1]] 输出: 2 说明已知城市 0 和城市 1 相连他们在一个省份。 第 2 个城市自己在一个省份。所以返回 2。示例 2输入: [[1,1,0], [1,1,1], [0,1,1]] 输出: 1 说明已知城市 0 和城市 1 直接相连城市 1 和城市 2 直接相连所以城市 0 和城市 2 间接相连所以他们三个在一个省份返回 1。注意N 在[1, 200]的范围内对于所有城市有M[i][i] 1每个城市与自身连通如果有M[i][j] 1则有M[j][i] 1邻接矩阵对称图为无向图。建模邻接矩阵 → 无向图 → 连通分量题目的关键一步是把给定矩阵看作图的邻接矩阵Adjacency Matrix矩阵的每个下标对应图中的一个顶点城市M[i][j] 1对应一条无向边(i, j)。这样问题就转化为求一个无向图中连通分量的个数英文版题解文档 547.friend-circles-en.md 中明确指出了这一转化思路。连通分量问题通常可以用DFS、BFS、并查集Union-Find三种方式解决。下面逐一展开。方法一并查集Union-Find思路并查集有一个功能是轻松计算连通分量而本题省份的个数本质上就是连通分量的个数因此用并查集可以完美解决见主文档 547.number-of-provinces.md 的思路小节。做法很简单初始时每个城市自成一个省份cnt记为N遍历邻接矩阵只需遍历i j的下三角即可因为矩阵对称遇到M[i][j] 1就将i与j所在的集合合并每成功合并一次cnt减 1。遍历结束后cnt就是省份连通分量的数量。Python 实现主文档给出的代码将并查集模板单独抽出find、union、connected都是典型模板方法class UF: parent {} cnt 0 def __init__(self, M): n len(M) for i in range(n): self.parent[i] i self.cnt 1 def find(self, x): while x ! self.parent[x]: x self.parent[x] return x def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] self.find(q) self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def findCircleNum(self, M: List[List[int]]) - int: n len(M) uf UF(M) for i in range(n): for j in range(i): if M[i][j] 1: uf.union(i, j) return uf.cnt复杂度分析时间复杂度平均O(logN)最坏的情况是O(N)。原因在于主文档的find实现没有做路径压缩当树退化成链时find、union、connected都会退化到O(N)空间复杂度使用了parent数组为O(N)。优化方向按大小合并 路径压缩主文档明确指出两条优化路径按大小按秩合并为每一个顶层元素维护一个size表示其连通分量的大小union时总是将小树拼接到大树上。这样可以避免树不断长高将树高控制在O(logN)级别路径压缩在find过程中将沿途节点直接挂到根节点上把树高压缩到常数级别配合按秩合并后find/union的均摊时间复杂度可以趋近O(1)。仓库的并查集专题文档 union-find.md 给出了同时包含路径压缩与按大小合并的完整模板class UF: def __init__(self, M): self.parent {} self.size {} self.cnt 0 # 初始化 parentsize 和 cnt # size 是一个哈希表记录每一个联通域的大小其中 key 是联通域的根value 是联通域的大小 # cnt 是整数表示一共有多少个联通域 for i in range(M): self.parent[i] i self.cnt 1 self.size[i] 1 def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上 使树尽量平衡 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_q] self.size[leader_p] else: self.parent[leader_q] leader_p self.size[leader_p] self.size[leader_q] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q)关于路径压缩的意义专题文档中有一个直观解释每次find都会从当前节点向上不断搜索直到根节点因此find的时间复杂度大致等于节点的深度如果不加控制树高可能等于节点数find会退化到O(N)。而路径压缩后树的平均高度不超过logN如果同时使用路径压缩与按秩合并时间复杂度趋近O(1)——更严谨的说法是“阿克曼函数的某个反函数”即近乎常数的均摊复杂度。下面是并查集解法在处理示例输入时的完整流程示意图图中展示了union(0,1)、union(0,2)、union(1,3)逐步合并的过程初始count 5每成功合并一次count减 1最终得到两个连通分量{0,1,2,3}与{4}因此省份数为 2。C 实现每日一题存档仓库的每日一题存档 daily/2019-08-11.md 给出了带路径压缩的 C 版本其核心思想完全一致可作为多语言对照class Solution { public: int findCircleNum(vectorvectorint M) { if (M.empty()) return 0; vectorint pre(M.size()); for(int i0; iM.size(); i) pre[i] i;//先各自为组组名也为自己的序号 int group M.size();//一开始有多少人就有多少个朋友圈当每出现一对朋友时就减1最后就是总的朋友圈数量了。 for(int i0; iM.size(); i) { for(int j0; jM.size(); j) { if (i ! j M[i][j] 1) { int x1 find(i, pre);//x1为i所属的组 int x2 find(j, pre);//x2为j所属的组 if (x1 ! x2) { //如果不属于同个朋友圈的话就把i归为j的组 pre[x1] x2; group--; } } } } return group; } private: int find(int x, vectorint pre) { //“pre[x] ”这句为路径压缩直接指向组的根节点下次查询时就快很多了。 return pre[x]x ? x : pre[x] find(pre[x], pre); } };这段代码中pre[x] find(pre[x], pre)的递归写法就是路径压缩让当前节点直接指向组的根节点下次查询时就能以O(1)的代价找到根。方法二DFS思路DFS 思路详见英文版文档 547.friend-circles-en.md从每个节点出发做 DFS用visited数组标记已访问节点每次 DFS 都会访问当前节点所有直接相连的节点在邻接矩阵的当前行中扫描M[i][j] 1且未访问的j一次完整的 DFS 恰好覆盖一个连通分量因此启动 DFS 的次数就是连通分量省份的个数。复杂度分析时间复杂度O(N * N)其中 N 是城市数量需要遍历整个N x N矩阵空间复杂度O(N)visited数组大小为 N。Java 实现class FindCirclesDFS { public int findCircleNumDFS(int[][] M) { if (M null || M.length 0 || M[0].length 0) return 0; int n M.length; int numCircles 0; boolean[] visited new boolean[n]; for (int i 0; i n; i) { if (!visited[i]) { dfs(M, i, visited, n); numCircles; } } return numCircles; } private void dfs(int[][] M, int i, boolean[] visited, int n) { for (int j 0; j n; j) { if (M[i][j] 1 !visited[j]) { visited[j] true; dfs(M, j, visited, n); } } } }每日一题存档的 DFS 变体daily/2019-08-11.md 还给出了一种用整型visited数组实现的等价写法便于对比public class Solution { public void dfs(int[][] M, int[] visited, int i) { for (int j 0; j M.length; j) { if (M[i][j] 1 visited[j] 0) { visited[j] 1; dfs(M, visited, j); } } } public int findCircleNum(int[][] M) { int[] visited new int[M.length]; int count 0; for (int i 0; i M.length; i) { if (visited[i] 0) { dfs(M, visited, i); count; } } return count; } }DFS 的遍历过程如下图所示从节点 0 出发依次访问 1、3、2同一连通分量内的节点在一次 DFS 中全部被标记之后从未访问的节点 4 再启动第二次 DFS方法三BFS层级遍历思路BFS 的思路同样详见英文版文档 547.friend-circles-en.md从一个节点出发访问其所有直接相连的节点即访问同一层级的全部节点使用visited数组标记已访问节点用队列保存待扩展节点每当从一个新的未访问节点启动 BFS 时计数加 1该次 BFS 覆盖的正是同一个连通分量。复杂度分析时间复杂度O(N * N)遍历整个矩阵空间复杂度O(N)队列与visited数组大小均为 N。Java 实现class FindCircleBFS { public int findCircleNumBFS(int[][] M) { if (M null || M.length 0) return 0; int numCircle 0; int n M.length; boolean[] visited new boolean[n]; QueueInteger queue new LinkedList(); for (int i 0; i n; i) { // already visited, skip if (visited[i]) continue; queue.add(i); while (!queue.isEmpty()) { int curr queue.poll(); visited[curr] true; for (int j 0; j n; j) { if (M[curr][j] 1 !visited[j]) { queue.add(j); } } } numCircle; } return numCircle; } }BFS 按层级扩散的过程如下图所示第 0 层只有节点 0第 1 层是 1 和 2第 2 层是 3节点 4 单独成连通分量三种方法对比与选择方法核心思想时间复杂度空间复杂度特点并查集合并相邻节点统计集合个数平均O(logN)最坏O(N)路径压缩 按秩合并后趋近O(1)O(N)parent 数组模板化程度高可扩展性强带权并查集、离线查询适合“多次动态询问连通性”的场景DFS一次 DFS 覆盖一个连通分量O(N * N)O(N)visited 数组实现最简单直观天然递归BFS一次 BFS 覆盖一个连通分量O(N * N)O(N)队列 visited层级遍历可顺便求最短路径等额外信息从源码结构看并查集是主文档problems/547.number-of-provinces.md与并查集专题thinkings/union-find.md共同推崇的解法原因在于并查集只回答“联通与否”而不关心“具体联通路径”其三个核心 APIfind/union/connected可以像模板一样套用在大量连通性问题中。并查集核心原理速览三个核心 APIfind(x)不断沿parent向上查找找到 x 所属集合的根代表元素。根满足parent[x] xconnected(p, q)判断find(p) find(q)若祖先相同则两点连通union(p, q)将其中一个节点挂到另一个节点的祖先上使两者祖先相同从而联通。parent[x] y表示 x 的父节点是 y。之所以用 parent 存储父节点而非用 children 存储子节点是因为并查集的核心需求是“找到某个元素的代表根”见 union-find.md 的形象解释小节。两个关键优化路径压缩find递归时将沿途节点的parent直接指向根把树高压缩到常数级别降低后续查找代价按秩按大小合并union时把小的树挂到大的树上避免树不断增高使树保持平衡。专题文档中的复杂度结论令 n 为图中点的个数空间复杂度为O(n)parent带权并查集还有 weight时间上路径压缩 按秩合并优化后union和find的均摊复杂度接近于O(1)更严谨的表达是O(log(m × Alpha(n)))其中 Alpha 是阿克曼函数的某个反函数若只做路径压缩或只做按秩合并则复杂度分别为O(logx)和O(logy)x、y 分别为合并与查找的次数。经典应用检测图是否有环并查集除了统计连通分量还常用来检测无向图中是否存在环只需对每条边先判断connected(a, b)若合并之前已经联通说明存在环见 union-find.md 的应用小节uf UF() for a, b in edges: if uf.connected(a, b): return False uf.union(a, b) return True此外并查集还是最小生成树经典算法 Kruskal 的基础。相关题目与拓展并查集专题文档 union-find.md 在“练习”一节推荐了一系列连通性问题与本题目547属于同一套路建议练手账户合并无权图连通性模板题等式方程的可满足性无权图连通性交换字符串中的元素无权图连通性检查边长度限制的路径是否存在带权图连通性上面的题目中前四道都是无权图的连通性问题第五道是带权图的连通性问题。判断一道题是否适用并查集核心信号是题目中出现连通、等价这类关系描述。总结LeetCode 547「省份数量」是一道非常典型的“连通分量计数”题目题目给出的N x N矩阵本质上就是图的邻接矩阵于是问题被规约为求无向图连通分量个数并查集是主文档首推的解法初始每个城市自成一省遍历矩阵下三角对M[i][j] 1执行union每成功合并一次计数减 1最终计数即省份数量。注意find若不压缩最坏会退化到O(N)通过按大小合并 路径压缩可将均摊复杂度降到趋近O(1)DFS / BFS通过visited数组标记访问一次遍历恰好覆盖一个连通分量启动遍历的次数即省份数时间复杂度为O(N²)空间复杂度O(N)。掌握本题的价值在于吃透“连通性”这一类问题的通用模板之后遇到 721 账户合并、990 等式方程的可满足性、1697 带权连通性等题目都可以直接套用并查集模板快速求解。更完整的并查集原理、带权并查集模板与练习清单可继续阅读仓库中的 并查集专题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考