企业官网建设流程全解析

在第 5 节中，我们学习了并查集的基本概念和实现。本节将深入讲解两种重要的优化技术：路径压缩和按秩合并，让并查集的效率达到理论最优。

1. 回顾：基本并查集的问题

1.1 基本实现

classUnionFind{private:vector<int>parent;public:UnionFind(intn):parent(n){for(inti=0;i<n;i++){parent[i]=i;// 初始时每个节点是自己的父节点}}// 查找根节点intfind(intx){while(parent[x]!=x){x=parent[x];}returnx;}// 合并两个集合voidunite(intx,inty){introotX=find(x);introotY=find(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 Compression）

2.1 核心思想

路径压缩：在查找根节点的过程中，将路径上的所有节点直接指向根节点。

压缩前：0 → 1 → 2 → 3 → 4 → 5 压缩后：0 → 5 1 → 5 2 → 5 3 → 5 4 → 5

2.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 5

2.3 迭代实现

如果担心递归栈溢出，可以使用迭代实现：

intfind(intx){introot=x;// 第一遍：找到根节点while(parent[root]!=root){root=parent[root];}// 第二遍：路径压缩while(parent[x]!=root){intnext=parent[x];parent[x]=root;x=next;}returnroot;}

2.4 图解路径压缩

初始状态： 5 | 4 | 3 | 2 | 1 | 0 执行 find(0) 后： 5 / | | \ \ 0 1 2 3 4

所有节点直接指向根节点，后续查找都是 O(1)。

3. 按秩合并（Union by Rank）

3.1 核心思想

按秩合并：总是将较矮的树合并到较高的树下，避免树变得过高。

「秩」可以理解为树的高度的上界。

3.2 实现

classUnionFind{private:vector<int>parent;vector<int>rank;// 秩数组public:UnionFind(intn):parent(n),rank(n,0){for(inti=0;i<n;i++){parent[i]=i;}}intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}voidunite(intx,inty){introotX=find(x);introotY=find(y);if(rootX==rootY)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 5

4. 路径压缩 + 按秩合并

4.1 组合使用

两种优化可以同时使用，效果更好：

classUnionFind{private:vector<int>parent;vector<int>rank;public:UnionFind(intn):parent(n),rank(n,0){for(inti=0;i<n;i++){parent[i]=i;}}// 路径压缩intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}// 按秩合并voidunite(intx,inty){introotX=find(x);introotY=find(y);if(rootX==rootY)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 时间复杂度分析

其中α(n)是反阿克曼函数，增长极其缓慢：

• α(1) = 1
• α(2) = 1
• α(2^65536) = 5

对于任何实际可想象的 n，α(n) ≤ 5，所以可以认为是常数时间。

5. 按大小合并（Union by Size）

5.1 替代方案

除了按秩合并，还可以按大小合并：总是将小树合并到大树下。

classUnionFind{private:vector<int>parent;vector<int>size;// 集合大小public:UnionFind(intn):parent(n),size(n,1){for(inti=0;i<n;i++){parent[i]=i;}}intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}voidunite(intx,inty){introotX=find(x);introotY=find(y);if(rootX==rootY)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. 完整实现：带路径压缩和按秩合并

#include<iostream>#include<vector>usingnamespacestd;classUnionFind{private:vector<int>parent;vector<int>rank;intcount;// 连通分量数public:UnionFind(intn):parent(n),rank(n,0),count(n){for(inti=0;i<n;i++){parent[i]=i;}}// 路径压缩intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}// 按秩合并voidunite(intx,inty){introotX=find(x);introotY=find(y);if(rootX==rootY)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(){// 测试：判断图的连通性intn=6;UnionFinduf(n);// 添加边uf.unite(0,1);uf.unite(1,2);uf.unite(3,4);cout<<"连通分量数："<<uf.getCount()<<endl;// 输出：3cout<<"0 和 2 连通："<<(uf.connected(0,2)?"是":"否")<<endl;// 是cout<<"0 和 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<(constEdge&other)const{returnweight<other.weight;}};intkruskalMST(intn,vector<Edge>&edges){sort(edges.begin(),edges.end());UnionFinduf(n);intmstWeight=0;intedgesUsed=0;for(constEdge&e:edges){if(!uf.connected(e.u,e.v)){uf.unite(e.u,e.v);mstWeight+=e.weight;edgesUsed++;if(edgesUsed==n-1)break;}}returnmstWeight;}

7.2 动态连通性问题

// 判断删除边后图是否仍然连通vector<bool>areConnected(intn,vector<pair<int,int>>&edges,vector<pair<int,int>>&queries){// 逆序处理：从最终状态开始，逐步添加边UnionFinduf(n);vector<bool>result;// 先添加所有不在查询中的边set<pair<int,int>>querySet(queries.begin(),queries.end());for(auto&e:edges){if(querySet.find(e)==querySet.end()){uf.unite(e.first,e.second);}}// 逆序处理查询reverse(queries.begin(),queries.end());for(auto&q: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(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();UnionFinduf(m*n);for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]==1){// 向右和向下合并if(j+1<n&&grid[i][j+1]==1){uf.unite(i*n+j,i*n+j+1);}if(i+1<m&&grid[i+1][j]==1){uf.unite(i*n+j,(i+1)*n+j);}}}}// 统计不同的根节点数set<int>roots;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]==1){roots.insert(uf.find(i*n+j));}}}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，可以认为是常数时间。

选择建议：

• 需要查询集合大小 → 按大小合并
• 否则 → 按秩合并或按大小合并都可以
• 无论如何都要路径压缩

下一节我们将学习最小生成树算法，解决另一个经典的图论问题。