高频必考！并查集：动态连通性“找根 + 合并”模板，面试必背

我们用DFS数过岛屿——那是“静态地求连通块”。如果问题是边一条条加进来随时问“这两点通了吗”“加这条边会不会成环”DFS每次重扫就太慢了。这时就轮到并查集Union-Find出场。它只干两件事find(x)找根union(x,y)合并。操作近乎O(1)是处理动态连通性的瑞士军刀。今天用LC.547「省份数量」把这套面试必背模板彻底打透——parent数组 路径压缩 按大小合并三件套一次到位。 题目速览 LC.54730秒读懂n个城市isConnected[i][j] 1表示i城与j城直接相连。省份是一组直接或间接相连的城市集合。返回省份数量。示例[[1,1,0],[1,1,0],[0,0,1]]→ 输出2城市0-1一省城市2一省示例[[1,0,0],[0,1,0],[0,0,1]]→ 输出3三城互不相连约束n ≤ 200矩阵对称对角线为1。 核心思路把连通性变成“认根”不同根数就是省份数DFS能做但不够优雅从每个未访问节点出发DFS走完整块连通分量——数岛的孪生版。能做但每次查“两点通不通”都得搜一遍不适合动态场景。并查集每个集合选一个“根”代表自己初始n个城市各成一派parent[i] i读邻接矩阵凡isConnected[i][j] 1就union(i, j)最后不同根的数量 连通分量省份数查询“i、j通不通”只需find(i) find(j)O(1)级别。 两个让并查集起飞的优化必背1. 路径压缩Path Compressionfind时把沿途节点直接挂到根上下次再查一步到位parent[x]parent[parent[x]]# 沿途挂到爷爷压缩链2. 按秩/大小合并Union by Rank/Sizeunion时把“矮的树”挂到“高的树”根下避免链化。单独按秩合并→ 树高O(logn)路径压缩 按秩合并→ 单次操作均摊O(α(n))α是阿克曼反函数增长极慢n取宇宙原子数都不到5——实际可视为常数时间。为什么并查集比DFS强本题一次性给全关系DFS完全够用。但并查集的杀手锏是动态性边一条条来随时问连通性随时判环加边前find(u)find(v)就说明会成环这种“在线/动态”场景 DFS 力不从心并查集游刃有余。️ 图解算法手把手走一遍isConnected [[1,1,0],[1,1,0],[0,0,1]]城市0,1,2初始parent [0, 1, 2]各自为根 读 (0,1)1 → union(0,1) 按大小合并0、1都单点把1挂到 0 parent [0, 0, 2] 读 (0,2)0 / (1,2)0 → 不连通跳过 读 (1,0) 已处理对称跳过对角线 (i,i) 跳过 最终 parent [0, 0, 2] 根为0代表城市0、1、根为2代表城市2 不同根集合{0,1}, {2} → 2 个省份 ✅关键观察union(0,1)后无论查find(0)还是find(1)都得到同一个根0——“认根即认亲”。若再加一条 (1,2)1则union(1,2)把根2挂到根0三城归一省。 代码实现Python JavaPython版完整模板路径压缩 按大小合并classSolution:deffindCircleNum(self,isConnected:List[List[int]])-int:nlen(isConnected)parentlist(range(n))# 初始各自为根size[1]*n# 每棵树大小用于按大小合并deffind(x):# 路径压缩whilex!parent[x]:parent[x]parent[parent[x]]# 沿途挂到爷爷xparent[x]returnxdefunion(x,y):# 按大小合并rx,ryfind(x),find(y)ifrxry:return# 已同根ifsize[rx]size[ry]:parent[rx]ry size[ry]size[rx]else:parent[ry]rx size[rx]size[ry]foriinrange(n):forjinrange(i1,n):# 只扫上三角避免重复ifisConnected[i][j]1:union(i,j)rootsset(find(i)foriinrange(n))returnlen(roots)# 不同根数 省份数Java版classSolution{privateint[]parent;privateint[]size;publicintfindCircleNum(int[][]isConnected){intnisConnected.length;parentnewint[n];sizenewint[n];for(inti0;in;i){parent[i]i;size[i]1;}for(inti0;in;i){for(intji1;jn;j){if(isConnected[i][j]1)union(i,j);}}intcnt0;for(inti0;in;i)if(parent[i]i)cnt;returncnt;}privateintfind(intx){// 路径压缩while(x!parent[x]){parent[x]parent[parent[x]];xparent[x];}returnx;}privatevoidunion(intx,inty){// 按大小合并intrxfind(x),ryfind(y);if(rxry)return;if(size[rx]size[ry]){parent[rx]ry;size[ry]size[rx];}else{parent[ry]rx;size[rx]size[ry];}}}⚠️防坑提醒必看parent初始parent[i]i自己就是自己的根。find用迭代写法避免深递归栈溢出。只遍历上三角ji矩阵对称减少一半union。“数根”两种写法统计parent[i]i或收集find(i)去重结果一致。⏱️ 复杂度分析面试必问版本时间空间路径压缩 按大小合并O(n²·α(n)) ≈ O(n²)O(n)朴素并查集O(n²·n)链化退化O(n)α(n)是阿克曼反函数n极大时也 5实际视为常数。比DFS的递归栈/visited矩阵更省空间。 举一反三4 道高频变体题题目变化点思路要点LC.200 岛屿数量网格连通块把相邻1当边union或DFSLC.684 冗余连接给树一条多余边找成环的那条边依次union首次find(u)find(v)即环边LC.1319 连通网络的操作次数最少连线使全网连通并查集求连通分量数c答案 c-1LC.990 等式方程的可满足性等式/不等式混合先union所有等式再检查不等式是否冲突 面试追问模拟提前准备惊艳全场Q1路径压缩 按秩合并为什么能降到O(α(n))单独按秩合并树高限制为O(logn)单独路径压缩单次可能O(n)但均摊小。两者结合时路径压缩不停“拍平”树按秩保证合并不乱长高。经势能分析证明单次操作均摊O(α(n))。α(n)增长比log还慢n取天文数字仍 5——实际当常数用。Q2并查集 vs DFS求连通分量怎么选静态图、只求一次连通块两者都行DFS代码更短。边逐步加入、反复回答“两点通不通 / 加边会不会成环”并查集天选每次查询/合并近乎O(1)DFS每次都得重搜。一句话静态用DFS动态用并查集。Q3并查集经典扩展有哪些① 找环边LC.684边依次union遇到find(u)find(v)说明这条边把已连通的两点又连了一次必成环② 最小生成树Kruskal用并查集判“加这条边会不会成环”③ 连通网络操作次数LC.1319先算现有c个连通分量最少补c-1条边即全连通。 实战小技巧刷题党必备口诀parent数组各自根find找根路径压union合并小的挂大的。模板并查集 parent size find union四件套背下来。防坑find用迭代防爆栈只扫上三角数根别数错。 实际应用场景不止是刷题社交网络朋友圈/共同群组合并图像处理连通区域标记海量像素动态合并网络监控链路动态增删时实时判断两节点是否可达编译器等价变量合并寄存器分配经典应用分布式系统分区检测 今日思考题如果面试官把LC.547改成“边一条条实时到来每加一条就问一次当前有几座省份”DFS还能胜任吗提示并查集每次加边只需一次union维护一个“当前根数”变量加边时若合并成功则根数-1。