当前位置： 首页 > java >正文

C++并集查找

java 2025/7/23 9:59:45

前言

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]=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
用栈记录操作记录。已经连通也要有记录。

封装类代码

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

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<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;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;
};

样例

力扣

难度分
【欧拉回路】【图论】【并集查找】765. 情侣牵手无
【C++图论 并集查找】2316. 统计无向图中无法互相到达点对数1604
【C++图论 并集查找】1319. 连通网络的操作次数1633
【C++图论 并集查找】2492. 两个城市间路径的最小分数1679
【C++并集查找 图论】1202. 交换字符串中的元素1855
【C++图论 并集查找】924. 尽量减少恶意软件的传播1868
【图论】【并集查找】【C++算法】928. 尽量减少恶意软件的传播 II1985
【C++ 并集查找】1722. 执行交换操作后的最小汉明距离1892
【图论】【广度优先】【 并集查找】2092 找出知晓秘密的所有专家2003
【C++图论 并集查找】947. 移除最多的同行或同列石头2034
C++二分查找或并集查找：2948交换得到字典序最小的数组2047
【并集查找】839. 相似字符串组2053
【C++ 同余 裴蜀定理 中位数贪心 并集查找】2607. 使子数组元素和相等2071
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价2108
【C++图论 并集查找】1579. 保证图可完全遍历2131
【最大公约 调和级数 并集查找】2709. 最大公约数遍历2171
【调和级数 并集查找】1627. 带阈值的图连通性2221
【并集查找 最大公约数 调和数】952. 按公因数计算最大组件大小2272
【并集查找】749. 隔离病毒2277
【并集查找 离线查询】1697. 检查边长度限制的路径是否存在2300
【广度优先搜索】【二分图】【并集查找】2493. 将节点分成尽可能多的组2415
【最大公约数 并集查找 调和级数】1998. 数组的最大公因数排序2429
【并集查找 图论】2421. 好路径的数目2444
【状态压缩 并集查找 图论】2157. 字符串分组2499
【图轮】【 最小生成树】【 并集查找】1489. 找到最小生成树里的关键边和伪关键边2571

洛谷普及+

【二分查找 并集查找】P6004 [USACO20JAN] Wormhole Sort S普及+
【图论 BFS染色 并集查找 】P3663 [USACO17FEB] Why Did the Cow Cross the Road III S普及+
【图论 并集查找】P3671 [USACO17OPEN] Where‘s Bessie? S普及+
【拓扑排序 并集查找】P8269 [USACO22OPEN] Visits S普及+
【贪心 逆向思考 并集查找 数学归纳法】P7162 [COCI 2020/2021 #2] Sjekira普及+
【并集查找】P7299 [USACO21JAN] Dance Mooves S普及+
【并集查找 逆向思考】P8097 [USACO22JAN] Farm Updates G普及+
【位运算 并集查找】P7973 [KSN2021] Binary Land普及+
【并集查找】P7991 [USACO21DEC] Connecting Two Barns S普及+
【并集查找 最小生成树】P8191 [USACO22FEB] Moo Network G普及+
【并集查找 启发性合并】P8710 [蓝桥杯 2020 省 AB1] 网络分析普及+
【并集查找 有向图 逆序思考】P8359 [SNOI2022] 垃圾回收普及+
【并集查找】8210 [THUPC 2022 初赛] 造计算机普及+
【并集查找 拓扑序】P9013 [USACO23JAN] Find and Replace S普及+
【最短路 并集查找】P9327 [CCC 2023 S4] Minimum Cost Roads普及+
【二分图 扩展域并集查找】P1525 [NOIP 2010 提高组] 关押罪犯普及+
【二分图 扩展域并集查找】P11409 西湖有雅座普及+
【单调栈 双连通 并集查找】P12169 [蓝桥杯 2025 省 C/Python A/Java C] 登山普及+
【并集查找】P12274 [蓝桥杯 2024 国 Python B] 设计普及+

样例整理时间

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++**实现。

http://www.xdnf.cn/news/9652.html

相关文章：

  • 关于scrapy在pycharm中run可以运行，但是debug不行的问题
  • 联想小新pro 14 重新安装系统提示acpi-bios-error错误的解决方法
  • VSCode远程开发-本地SSH隧道保存即时修改
  • 三轴云台之抗扰动技术篇
  • Text-to-SQL评估体系：从Spider 1.0数据集到2.0框架的跨越与革新
  • 9.安卓逆向2-frida hook技术-frida基本使用-frida-ps指令
  • 202505系分论文《论信息系统开发方法及应用》
  • C++学习细节回顾(汇总三)
  • Linux命令行命令自动补全
  • 自动化测试常见函数(上篇）
  • 如何使用 Python 的胶水语言特性
  • 小白成长之路-Linux程序管理（二）
  • matlab全息技术中的菲涅尔仿真成像
  • LLM Coding
  • 结构体定义嵌套定义
  • CRM系统的功能模块划分
  • Python编程4——函数
  • 点云保存为pcd的一个例子
  • 微前端架构设计与实战示例
  • 嵌入式仿真平台如何重塑I²C协议教学：以AT24C02实验为例
  • linux——TCP问题
  • 自举升压方法
  • 高通滤波和低通滤波
  • Wi-Fi 6E/7法规认证的要求
  • AAOS系列之(五) ---CarPowerService 电源管理模块分析
  • ros2--串口通信
  • Lesson 9 防火墙 iptables 和 firewalld
  • SpringBoot 自动装配原理深度解析：从源码到实践
  • csdn_export_md
  • Linux特殊符号