C++并集查找

前言

C++图论
C++算法与数据结构
本博文代码打包下载

基本概念

并查集（Union-Find）是一种用于处理动态连通性（直接或间接相连）的数据结构，主要支持两种操作：union 和 find。通过这两个基本操作，可以高效地管理一组元素之间的连通关系。
Find: 查找节点所在有向树的根。
Union: 将两个不同的有向图合并为一棵树。

暴力做法

并集查找处理无向图的数据结构：有向森林，每棵树都是内向树。连通子图都直接或间接指向根，根出度为0，其它节点出度为1。vPar记录各节点的父节点。
Find(u)函数寻找u所在有向树的根（最远祖先）：

while(-1!= vPar[u]){ u =vPar}return u;

判断u和v是否连通：

returnFind(u)==Find(v)

连通：

root1 =Find(u); root2 =Find(v); 如果root1和root2相等，直接返回。否则会有自环。 vPar[root1]= root2;

初始和合并都是有向森林

可以用数学归纳法证明。
初始：所有连通子图都是只有一个节点的有向树。
合并前后：
root1是根，出度0。合并后不是根，出度为1。
root2合并前后都是根，出度为0，不变。
其它节点合并前后都不是根，出度不变。
合并前后：v节点所在子图都直接或间接指向root2。
合并后：u所在子树通过u间接指向root2。

时间复杂度

合并和查找都是O(n)

启发式合并（UNION BY RANK）

合并前，u、v所在子树的节点数分别为mu、mv。
{ v P a r [ r o o t 1 ] = r o o t 2 u 树所有节点层次 + 1 ， v 子树层次不变。 m u < = m v v P a r [ r o o t 2 ] = r o o t 1 v 树所有节点层次 + 1 ， u 子树层次不变 其它 \begin{cases} vPar[root1]= root2 & u树所有节点层次+1，v子树层次不变。 & mu <= mv \\ vPar[root2]=root1 & v树所有节点层次+1，u子树层次不变& 其它 \end{cases} {vPar[root1]=root2vPar[root2]=root1​u树所有节点层次+1，v子树层次不变。v树所有节点层次+1，u子树层次不变​mu<=mv其它​
任意节点合并的次数不会超过 l o g 2 n log2n log2n，否则合并此树的节点数超过n。被合并一次层次数+1，故所有节点的层次不互已超过 l o g 2 n log2n log2n。

路径压缩（PATH COMPRESSION）

路径压缩的优点在于它的简单性和有效性。尽管单次 find 的时间复杂度可能较高，但由于摊还分析的结果表明，经过多次操作后，平均时间复杂度接近常数 ( O(\alpha(n)) )，其中 ( \alpha(n) ) 是反阿克曼函数，增长极其缓慢}
u及u所有的祖先都直接连通root2。
合并和查找都是O(log2n)

可撤销并集查找

以启发式合并为基础。每次连通：
vPar[root1]= root2。 我们记录root1、修改之前的x=vPar[root1]。
vCnt[root2] += vCnt[root1]，我们记录root2，y=vCnt[root1]。
撤销时：
vPar[root1] = x vCnt[root2] -=y
用栈记录操作记录。已经连通也要有记录。

按秩和并

层次小的指向层次大的，层次不会超过logN,故连通和查询的时间复杂度都是O(logN)。可以实现带权并集查找，主要包括：路径最小边权最大生成树、路径最大边权最小生成树、相同起点终点任意路径边权必须相等。

路径最小边权最大生成树

g( p )是路径p中，最小边权。
f(u,v)是某图中u到v所有路径最大g( p ) ，假定uv连通。
将边权降序排序后，依次枚举uv。如果uv已经连通，忽略；否则连通。
性质一：原图G，并集查找图uf ，任意两点uv的连通性相同。
性质二：原图G，并集查找图uf ，任意两点uv的f(u,v)相等。G的边权就是原始边权。uf中u的根是g1,v的根是g2，如果 g 1 ≠ g 2 g1 \neq g2 g1=g2。如果最终是 g 1 → g 2 g1 \rightarrow g2 g1→g2，则此边的边权（简称g1边)是uv的边权w；如果 g 2 → g 1 g2 \rightarrow g1 g2→g1此边的边权也是w。
如果uv连通，其最最近公共祖先为g，则uf中 u → g → v u \rightarrow g \rightarrow v u→g→v的最小边权，就是G中f(u,v)。
性质三；n1的父节点是n2，n2的父节点是n3。则 n 1 → n 2 的边权 ≥ n 2 → n 3 的边权 n1 \rightarrow n2的边权\ge n2 \rightarrow n3的边权 n1→n2的边权≥n2→n3的边权。先加的边边权大，后加的边权小。只有各子树的根才会增加边，当 n 2 → n 3 n2 \rightarrow n3 n2→n3时，说明n2此时是根，即n1现在及未来不是根。

重构树(Kruskal’s Reconstruction Tree)

可以看成”路径最小边权最大生成树“的进一步扩展。
按边权从大到小排序，如果已经连通忽略。
共2N-1个节点， 0 ∼ N − 1 0 \sim N-1 0∼N−1是真实节点， i ∈ [ N , 2 × N − 1 ] i \in [N,2\times N-1] i∈[N,2×N−1]是虚拟节点，第i-N条有效边（非忽略边）添加后，此边所在区域。求点权就是第 i − N i-N i−N条有效边的边权。真实节点的点权可以看成无限大。
性质一：重构树中,uv的简单路径经过的最小点权。就是原图G中,u、v 任意”路径最小边权“的最大值。
性质二：任意子树x，x节点的点权 ≤ \le ≤任意子孙节点的点权。
性质三：某节点g1的点权 ≥ P \ge P ≥P，g1子树的真实节点u,v，则原图一定存在边权全 ≥ \ge ≥P的路径。即uv在重构树简单路径种经过的虚拟节点对应的边。
性质四：任意真实节点u，某祖先g1，g1的父节点是g2。 g 1 点权 ≥ P > g 2 点权 g1点权 \ge P > g2点权 g1点权≥P>g2点权.非g1子树的任意节点v，都和u不存在边权d都 ≥ P \ge P ≥P的路径。注意：重构树的层次可能是N，所有要用树上倍增求g1,g2。

封装类代码

无向图的并集查找（路径压缩）

classCUnionFind{public:CUnionFind(int iSize):m_vNodeToRegion(iSize){for(int i =0; i < iSize; i++){ m_vNodeToRegion[i]= i;} m_iConnetRegionCount = iSize;}CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size()){for(int i =0; i < vNeiBo.size(); i++){for(constauto& n : vNeiBo[i]){Union(i, n);}}}intGetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if(iNode == iConnectNO){return iNode;}return iConnectNO =GetConnectRegionIndex(iConnectNO);}voidUnion(int iNode1,int iNode2){constint iConnectNO1 =GetConnectRegionIndex(iNode1);constint iConnectNO2 =GetConnectRegionIndex(iNode2);if(iConnectNO1 == iConnectNO2){return;} m_iConnetRegionCount--;if(iConnectNO1 > iConnectNO2){ m_vNodeToRegion[iConnectNO1]= iConnectNO2;}else{ m_vNodeToRegion[iConnectNO2]= iConnectNO1;}}boolIsConnect(int iNode1,int iNode2){returnGetConnectRegionIndex(iNode1)==GetConnectRegionIndex(iNode2);}intGetConnetRegionCount()const{return m_iConnetRegionCount;}//vector<int> GetNodeCountOfRegion()//各联通区域的节点数量//{// const int iNodeSize = m_vNodeToRegion.size();// vector<int> vRet(iNodeSize);// for (int i = 0; i < iNodeSize; i++)// {// vRet[GetConnectRegionIndex(i)]++;// }// return vRet;//} std::unordered_map<int, vector<int>>GetNodeOfRegion(){ std::unordered_map<int, vector<int>> ret;constint iNodeSize = m_vNodeToRegion.size();for(int i =0; i < iNodeSize; i++){ ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}private: vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;};

实时更新各连通区域节点的并集查找

//启发式合并，实时更新各连通区域的节点classCUnionFindNodes:publicCUnionFind{public:CUnionFindNodes(int n):CUnionFind(n){ m_nodes.resize(n);for(int i =0; i < n; i++){ m_nodes[i].emplace_back(i);}}voidUnion(int iNode1,int iNode2){int g0 =GetConnectRegionIndex(iNode1);int g1 =GetConnectRegionIndex(iNode2);if(g0 == g1){return;}CUnionFind::Union(iNode1, iNode2);if(g1 ==GetConnectRegionIndex(g0)){swap(g0, g1);}if(m_nodes[g1].size()> m_nodes[g0].size()){swap(m_nodes[g1], m_nodes[g0]);} m_nodes[g0].insert(m_nodes[g0].end(), m_nodes[g1].begin(), m_nodes[g1].end()); m_nodes[g1].clear();} vector<vector<int>> m_nodes;};

无向图的并集查找

如果一条会形成环或出度为2，忽略。

classCUnionFindDirect{public:CUnionFindDirect(int iSize){ m_vRoot.resize(iSize);iota(m_vRoot.begin(), m_vRoot.end(),0);}voidConnect(bool& bConflic,bool& bCyc,int iFrom,int iTo){ bConflic = bCyc =false;if(iFrom != m_vRoot[iFrom]){ bConflic =true;}Fresh(iTo);if(m_vRoot[iTo]== iFrom){ bCyc =true;}if(bConflic || bCyc){return;} m_vRoot[iFrom]= m_vRoot[iTo];}intGetMaxDest(int iFrom){Fresh(iFrom);return m_vRoot[iFrom];}private:intFresh(int iNode){if(m_vRoot[iNode]== iNode){return iNode;}return m_vRoot[iNode]=Fresh(m_vRoot[iNode]);} vector<int> m_vRoot;};

可撤销的并集查找

classCUnDoUnionFind{public:CUnDoUnionFind(int N):m_par(N,-1),m_cnt(N,1){};intFind(int x){while(-1!= m_par[x]){ x = m_par[x];}return x;}voidUnion(int u,int v){int root1 =Find(u);int root2 =Find(v);if(root1 == root2){ m_record.emplace(root1, m_par[root1], root2,0);return;}if(m_cnt[root1]> m_cnt[root2]){swap(u, v);swap(root1, root2);} m_record.emplace(root1, m_par[root1], root2, m_cnt[root1]); m_par[root1]= root2; m_cnt[root2]+= m_cnt[root1];}boolUndo(){if(m_record.empty()){returnfalse;}constauto[root1, par, root2, cnt]= m_record.top(); m_record.pop(); m_par[root1]= par; m_cnt[root2]-= cnt;returntrue;} vector<int> m_par, m_cnt; stack<tuple<int,int,int,int>> m_record;};

带权并集查找

classCUnionFundW{public:CUnionFundW(int N):m_par(N),m_rank(N,1){for(int i =0; i < N; i++){ m_par[i]= i;}}//返回值：{被合并的连通区域的根root1,root1是不是node1的根}。连通的效果是增加边root1到root2。 pair<int,bool>Union(int node1,int node2){constauto&[root1, le1]=GetRootLeve(node1);constauto&[root2, le2]=GetRootLeve(node2);if(root1 == root2){return{-1,false};}if(m_rank[root1]== m_rank[root2]){ m_par[root1]= root2; m_rank[root2]++;return{ root1,true};}elseif(m_rank[root1]< m_rank[root2]){ m_par[root1]= root2;return{ root1,true};} m_par[root2]= root1;return{ root2,false};} tuple<int, vector<int>, vector<int>>LCA(int node1,int node2){//node1和node2相等或不在一个连通区域为空，否则路径的所有的边auto[root1, le1]=GetRootLeve(node1);auto[root2, le2]=GetRootLeve(node2); vector<int> ans1, ans2;if(root1 != root2){returnmake_tuple(-1, ans1, ans2);}for(; le2 > le1; le2--){ ans2.emplace_back(node2); node2 = m_par[node2];}for(; le1 > le2; le1--){ ans1.emplace_back(node1); node1 = m_par[node1];}for(; node1 != node2; node1 = m_par[node1], node2 = m_par[node2]){ ans1.emplace_back(node1); ans2.emplace_back(node2);}returnmake_tuple(node1, ans1, ans2);}boolIsConnet(int node1,int node2){auto[root1, le1]=GetRootLeve(node1);auto[root2, le2]=GetRootLeve(node2);return root1 == root2;} pair<int,int>GetRootLeve(int node)const{int leve =0;int root = node;while(root != m_par[root]){ root = m_par[root]; leve++;}return{ root,leve };} vector<int> m_par; vector<int> m_rank;};

样例

力扣

洛谷普及+

样例整理时间

2025-5-25

投票

# 扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。