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是否连通：
return Find(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]=root1u树所有节点层次+1，v子树层次不变。v树所有节点层次+1，u子树层次不变mu<=mv其它
任意节点合并的次数不会超过 log2n log2n log2n，否则合并此树的节点数超过n。被合并一次层次数+1，故所有节点的层次不互已超过 log2n 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，如果 g1≠g2 g1 \\neq g2 g1=g2。如果最终是 g1→g2 g1 \\rightarrow g2 g1→g2，则此边的边权（简称g1边)是uv的边权w；如果 g2→g1 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。则 n1→n2的边权≥n2→n3的边权 n1 \\rightarrow n2的边权\\ge n2 \\rightarrow n3的边权 n1→n2的边权≥n2→n3的边权。先加的边边权大，后加的边权小。只有各子树的根才会增加边，当 n2→n3 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。 g1点权≥P>g2点权 g1点权 \\ge P > g2点权 g1点权≥P>g2点权.非g1子树的任意节点v，都和u不存在边权d都 ≥P \\ge P ≥P的路径。注意：重构树的层次可能是N，所有要用树上倍增求g1,g2。
封装类代码
无向图的并集查找（路径压缩）
class CUnionFind{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 (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){m_vNodeToRegion[iConnectNO1] = iConnectNO2;}else{m_vNodeToRegion[iConnectNO2] = iConnectNO1;}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}//vector GetNodeCountOfRegion()//各联通区域的节点数量//{//const int iNodeSize = m_vNodeToRegion.size();//vector 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;const int 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;};实时更新各连通区域节点的并集查找
//启发式合并，实时更新各连通区域的节点class CUnionFindNodes : public CUnionFind {public:CUnionFindNodes(int n) :CUnionFind(n) {m_nodes.resize(n);for (int i = 0; i < n; i++) {m_nodes[i].emplace_back(i);}}void Union(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，忽略。
class CUnionFindDirect{public:CUnionFindDirect(int iSize){m_vRoot.resize(iSize);iota(m_vRoot.begin(), m_vRoot.end(), 0);}void Connect(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];}int GetMaxDest(int iFrom){Fresh(iFrom);return m_vRoot[iFrom];}private:int Fresh(int iNode){if (m_vRoot[iNode] == iNode){return iNode;}return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);}vector<int> m_vRoot;};可撤销的并集查找
class CUnDoUnionFind {public:CUnDoUnionFind(int N) :m_par(N, -1), m_cnt(N, 1) {};int Find(int x) {while (-1 != m_par[x]) { x = m_par[x]; }return x;}void Union(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];}bool Undo() {if (m_record.empty()) { return false; }const auto [root1, par, root2, cnt] = m_record.top(); m_record.pop();m_par[root1] = par;m_cnt[root2] -= cnt;return true;}vector<int> m_par, m_cnt;stack<tuple<int, int, int, int>> m_record;};带权并集查找
class CUnionFundW{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) {const auto& [root1, le1] = GetRootLeve(node1);const auto& [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 };}else if (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) {return make_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);}return make_tuple(node1, ans1, ans2);}bool IsConnet(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
投票
# 扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
