【算法】小白也能懂 · 第 18 节：并查集进阶（路径压缩与按秩合并）

在第 5 节中我们学习了并查集的基本概念和实现。本节将深入讲解两种重要的优化技术路径压缩和按秩合并让并查集的效率达到理论最优。1. 回顾基本并查集的问题1.1 基本实现classUnionFind{private:vectorintparent;public:UnionFind(intn):parent(n){for(inti0;in;i){parent[i]i;// 初始时每个节点是自己的父节点}}// 查找根节点intfind(intx){while(parent[x]!x){xparent[x];}returnx;}// 合并两个集合voidunite(intx,inty){introotXfind(x);introotYfind(y);if(rootX!rootY){parent[rootX]rootY;}}// 判断是否在同一集合boolconnected(intx,inty){returnfind(x)find(y);}};1.2 问题树可能退化成链考虑以下操作序列UnionFinduf(6);uf.unite(0,1);uf.unite(1,2);uf.unite(2,3);uf.unite(3,4);uf.unite(4,5);形成的树结构0 → 1 → 2 → 3 → 4 → 5此时查找find(0)需要遍历整条链时间复杂度退化为 O(n)。2. 路径压缩Path Compression2.1 核心思想路径压缩在查找根节点的过程中将路径上的所有节点直接指向根节点。压缩前0 → 1 → 2 → 3 → 4 → 5 压缩后0 → 5 1 → 5 2 → 5 3 → 5 4 → 52.2 递归实现intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);// 递归查找并压缩路径}returnparent[x];}执行过程find(0): parent[0] 1 find(1): parent[1] 2 find(2): parent[2] 3 find(3): parent[3] 4 find(4): parent[4] 5 find(5): return 5 parent[4] 5 return 5 parent[3] 5 return 5 parent[2] 5 return 5 parent[1] 5 return 5 parent[0] 5 return 52.3 迭代实现如果担心递归栈溢出可以使用迭代实现intfind(intx){introotx;// 第一遍找到根节点while(parent[root]!root){rootparent[root];}// 第二遍路径压缩while(parent[x]!root){intnextparent[x];parent[x]root;xnext;}returnroot;}2.4 图解路径压缩初始状态 5 | 4 | 3 | 2 | 1 | 0 执行 find(0) 后 5 / | | \ \ 0 1 2 3 4所有节点直接指向根节点后续查找都是 O(1)。3. 按秩合并Union by Rank3.1 核心思想按秩合并总是将较矮的树合并到较高的树下避免树变得过高。「秩」可以理解为树的高度的上界。3.2 实现classUnionFind{private:vectorintparent;vectorintrank;// 秩数组public:UnionFind(intn):parent(n),rank(n,0){for(inti0;in;i){parent[i]i;}}intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}voidunite(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY)return;// 按秩合并if(rank[rootX]rank[rootY]){parent[rootX]rootY;// 矮树合并到高树下}elseif(rank[rootX]rank[rootY]){parent[rootY]rootX;}else{parent[rootY]rootX;rank[rootX];// 高度相同时合并后高度1}}boolconnected(intx,inty){returnfind(x)find(y);}};3.3 图解按秩合并初始rank [0, 0, 0, 0, 0, 0] unite(0, 1): rank[0] rank[1]合并后 rank[0] 1 0 | 1 unite(2, 3): rank[2] rank[3]合并后 rank[2] 1 2 | 3 unite(0, 2): rank[0] rank[2]合并后 rank[0] 2 0 / \ 1 2 | 3 unite(4, 5): rank[4] rank[5]合并后 rank[4] 1 4 | 5 unite(0, 4): rank[0] rank[4]4 合并到 0 下 0 / | \ 1 2 4 | | 3 54. 路径压缩 按秩合并4.1 组合使用两种优化可以同时使用效果更好classUnionFind{private:vectorintparent;vectorintrank;public:UnionFind(intn):parent(n),rank(n,0){for(inti0;in;i){parent[i]i;}}// 路径压缩intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}// 按秩合并voidunite(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY)return;if(rank[rootX]rank[rootY]){parent[rootX]rootY;}elseif(rank[rootX]rank[rootY]){parent[rootY]rootX;}else{parent[rootY]rootX;rank[rootX];}}boolconnected(intx,inty){returnfind(x)find(y);}};4.2 时间复杂度分析实现方式find 操作unite 操作总复杂度m 次操作基本实现O(n)O(n)O(m × n)仅路径压缩均摊 O(α(n))O(α(n))O(m × α(n))仅按秩合并O(log n)O(log n)O(m × log n)两者结合均摊 O(α(n))O(α(n))O(m × α(n))其中α(n)是反阿克曼函数增长极其缓慢α(1) 1α(2) 1α(2^65536) 5对于任何实际可想象的 nα(n) ≤ 5所以可以认为是常数时间。5. 按大小合并Union by Size5.1 替代方案除了按秩合并还可以按大小合并总是将小树合并到大树下。classUnionFind{private:vectorintparent;vectorintsize;// 集合大小public:UnionFind(intn):parent(n),size(n,1){for(inti0;in;i){parent[i]i;}}intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}voidunite(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY)return;// 按大小合并if(size[rootX]size[rootY]){parent[rootX]rootY;size[rootY]size[rootX];}else{parent[rootY]rootX;size[rootX]size[rootY];}}intgetSize(intx){returnsize[find(x)];}boolconnected(intx,inty){returnfind(x)find(y);}};5.2 按秩合并 vs 按大小合并特性按秩合并按大小合并维护信息树的高度上界集合大小代码复杂度稍复杂更简单时间复杂度相同相同额外功能无可查询集合大小建议需要查询集合大小时用按大小合并否则两者皆可。6. 完整实现带路径压缩和按秩合并#includeiostream#includevectorusingnamespacestd;classUnionFind{private:vectorintparent;vectorintrank;intcount;// 连通分量数public:UnionFind(intn):parent(n),rank(n,0),count(n){for(inti0;in;i){parent[i]i;}}// 路径压缩intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}// 按秩合并voidunite(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY)return;if(rank[rootX]rank[rootY]){parent[rootX]rootY;}elseif(rank[rootX]rank[rootY]){parent[rootY]rootX;}else{parent[rootY]rootX;rank[rootX];}count--;// 合并后连通分量减 1}boolconnected(intx,inty){returnfind(x)find(y);}intgetCount(){returncount;}};intmain(){// 测试判断图的连通性intn6;UnionFinduf(n);// 添加边uf.unite(0,1);uf.unite(1,2);uf.unite(3,4);cout连通分量数uf.getCount()endl;// 输出3cout0 和 2 连通(uf.connected(0,2)?是:否)endl;// 是cout0 和 3 连通(uf.connected(0,3)?是:否)endl;// 否uf.unite(2,4);cout合并 2 和 4 后0 和 3 连通(uf.connected(0,3)?是:否)endl;// 是cout连通分量数uf.getCount()endl;// 输出2return0;}7. 实际应用7.1 Kruskal 最小生成树structEdge{intu,v,weight;booloperator(constEdgeother)const{returnweightother.weight;}};intkruskalMST(intn,vectorEdgeedges){sort(edges.begin(),edges.end());UnionFinduf(n);intmstWeight0;intedgesUsed0;for(constEdgee:edges){if(!uf.connected(e.u,e.v)){uf.unite(e.u,e.v);mstWeighte.weight;edgesUsed;if(edgesUsedn-1)break;}}returnmstWeight;}7.2 动态连通性问题// 判断删除边后图是否仍然连通vectorboolareConnected(intn,vectorpairint,intedges,vectorpairint,intqueries){// 逆序处理从最终状态开始逐步添加边UnionFinduf(n);vectorboolresult;// 先添加所有不在查询中的边setpairint,intquerySet(queries.begin(),queries.end());for(autoe:edges){if(querySet.find(e)querySet.end()){uf.unite(e.first,e.second);}}// 逆序处理查询reverse(queries.begin(),queries.end());for(autoq:queries){result.push_back(uf.connected(q.first,q.second));uf.unite(q.first,q.second);// 添加边}reverse(result.begin(),result.end());returnresult;}7.3 图像处理连通区域标记intcountIslands(vectorvectorintgrid){intmgrid.size(),ngrid[0].size();UnionFinduf(m*n);for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){// 向右和向下合并if(j1ngrid[i][j1]1){uf.unite(i*nj,i*nj1);}if(i1mgrid[i1][j]1){uf.unite(i*nj,(i1)*nj);}}}}// 统计不同的根节点数setintroots;for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){roots.insert(uf.find(i*nj));}}}returnroots.size();}8. 常见问题与陷阱8.1 忘记路径压缩问题find 操作退化为 O(n)解决始终使用路径压缩8.2 按秩合并时忘记更新秩问题秩信息不准确影响合并决策解决只在高度相同时更新秩if(rank[rootX]rank[rootY]){rank[rootX];// 只有这里才更新}8.3 路径压缩后秩不再精确现象路径压缩后秩只是高度的上界不再是精确值影响不影响算法正确性和时间复杂度8.4 未压缩路径查询集合大小问题如果用parent数组计算大小路径压缩后会出错解决使用独立的size数组9. 总结并查集的两种核心优化路径压缩让树变得更扁平find 操作接近 O(1)按秩合并避免树过高保证树的平衡组合使用后每次操作的均摊时间复杂度为 O(α(n))α(n) ≤ 5可以认为是常数时间。选择建议需要查询集合大小 → 按大小合并否则 → 按秩合并或按大小合并都可以无论如何都要路径压缩下一节我们将学习最小生成树算法解决另一个经典的图论问题。