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

无向图的并集查找

如果一条会形成环或出度为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 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 m_par, m_cnt;
	stack m_record;
};

样例

力扣

洛谷普及+

样例整理时间

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