进阶数据结构——并查集

发布于：2025-02-13 ⋅ 阅读:(12) ⋅ 点赞:(0)

在这里插入图片描述

一、并查集的核心思想与本质

核心思想：并查集（Disjoint Set Union，DSU）是一种用于管理元素分组的数据结构，支持以下操作：
1. 查找（Find）：确定元素所属的集合（通常用代表元素表示）。
2. 合并（Union）：将两个集合合并为一个集合。
本质：通过树形结构和路径压缩、按秩合并等优化技术，实现高效的集合管理。

二、并查集的基本操作

1. 初始化
• 每个元素初始时是一个独立的集合，父节点指向自己。

2. 查找（Find）
• 查找元素的根节点（代表元素），同时进行路径压缩。

3. 合并（Union）
• 将两个集合合并，按秩合并优化。

三、并查集的应用场景

1. 连通性问题
• 判断图中节点是否连通：将节点分组，判断是否属于同一集合。
• 示例：LeetCode 547. 省份数量。
2. 动态连通性
• 实时合并与查询：在动态变化的图中，实时判断节点是否连通。
• 示例：Kruskal 算法中的最小生成树。
3. 分组与分类
• 元素分组：将元素按某种规则分组，如社交网络中的朋友圈。
• 示例：LeetCode 200. 岛屿数量。

四、并查集的优化技术

1. 路径压缩
• 目标：使树的高度尽可能小，提高查找效率。
• 实现：在查找过程中，将节点的父节点直接指向根节点。
2. 按秩合并
• 目标：避免树的高度过高，保持树的平衡。
• 实现：将较小的树合并到较大的树中，更新秩。

五、并查集的复杂度分析

时间复杂度
• 查找（Find）：

O(α(n))，其中 α(n) 是反阿克曼函数，接近常数时间。
• 合并（Union）：
𝑂
(𝛼(𝑛))。
空间复杂度
• 存储父节点和秩：
𝑂(𝑛)

六、并查集的变种与高阶应用

1. 带权并查集
• 特点：在并查集中维护额外的权值信息（如距离、大小）。
• 应用：解决带权图的连通性问题。
2. 可持久化并查集
• 特点：支持历史版本的查询与合并。
• 应用：需要回溯操作的场景。
3. 动态并查集
• 特点：支持动态添加和删除元素。
• 应用：实时更新的连通性问题。


七、常见陷阱与调试技巧

1. 初始化问题
• 未正确初始化：确保每个元素的父节点初始时指向自己。
2. 路径压缩与按秩合并的冲突
• 同时使用：路径压缩和按秩合并可以同时使用，不会冲突。
3. 调试方法
• 打印父节点数组：在每次操作后输出父节点数组，检查是否正确。
• 可视化树结构：手动画出树形结构，检查路径压缩和合并操作。

八、并查集的常见算法模版（c++）

1.朴素算法

这个算法数据范围小的可以用，数据范围大了就会超时，所以要优化算法。

例题

并查集

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSetSimple {
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_set;
};

void UFSetSimple::init(int maxId) {
	m_set.clear();
	for (int i = 1; i <= maxId; i++) {
		m_set[i] = i;
	}
}

int UFSetSimple::Find(int id) {
	return m_set[id];
}

bool UFSetSimple::Union(int id1, int id2){
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	for (int i = 1; i <= m_set.size(); i++) {
		if (m_set[i] == s2) {
			m_set[i] = s1;
		}
	}
	return true;
}



int main() {
	int n, m;
	cin >> n >> m;
	UFSetSimple ufs;
	ufs.init(n);
	while (m--) {
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) {
			ufs.Union(x, y);
		}
		else if (z == 2) {
			if (ufs.Find(x) == ufs.Find(y)) cout << 'Y' << endl;
			else cout << 'N' << endl;
		}
	}

	return 0;
}

2.森林算法

同样这个算法的时间复杂度也没有被优化

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSetForest {
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int>m_far;
};

void UFSetForest::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSetForest::Find(int id) {
	int p = m_far[id];
	while (p != m_far[p]) {
		p = m_far[p];
	}
	return p;
}

bool UFSetForest::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}


int main() {
	int n, m;
	cin >> n >> m;
	UFSetForest uf;
	uf.init(n);
	while (m--) {
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) {
			uf.Union(x, y);
		}
		else {
			if (uf.Find(x) != uf.Find(y))cout << 'N' << endl;
			else cout << 'Y' << endl;
		}
	}

	return 0;
}

3.启发式合并

像这个就优化很多了，但是还有点小瑕疵。

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSetStar {
private:
	unordered_map<int, int>m_far;		//m_far[x]代表这个棵树上父结点编号
	unordered_map<int, int>m_height;	//m_height[x]代表以x为根节点的数高
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
};

void UFSetStar::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
		m_height[i] = 1;
	}
}

int UFSetStar::Find(int id) {
	int p = m_far[id];
	while (p != m_far[p]) {
		p = m_far[p];
	}
	return p;
}

bool UFSetStar::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	if (m_height[s1] < m_height[s2]) {
		m_far[s1] = s2;
	}
	else if (m_height[s1] > m_height[s2]) {
		m_far[s2] = s1;
	}
	else {
		m_height[s1]++;		//两棵树高度如果相同那么它们合并起来的高度必然加1
		m_far[s2] = s1;
	}
	return true;
}


int main() {
	UFSetStar ufs;
	int n, m;
	cin >> n >> m;
	ufs.init(n);
	while (m--) {
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) {
			ufs.Union(x, y);
		}
		else if (z == 2) {
			if (ufs.Find(x) == ufs.Find(y))cout << 'Y' << endl;
			else cout << 'N' << endl;
		}
	}

	return 0;
}

4.路径压缩

这个模板就直接可以放心大胆的使用。

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSet {
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int>m_far;
};

void UFSet::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id) {		//递归查找这颗数的根结点
	if (m_far[id] == id)return id;
	return m_far[id] = Find(m_far[id]);		
}

bool UFSet::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}


int main() {
	int n, m;
	cin >> n >> m;
	UFSet uf;
	uf.init(n);
	while (m--) {
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) {
			uf.Union(x, y);
		}
		else {
			if (uf.Find(x) != uf.Find(y))cout << 'N' << endl;
			else cout << 'Y' << endl;
		}
	}

	return 0;
}

5.kruskal

【模板】最小生成树

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

class UFSet {
private:
	unordered_map<int, int>m_far;
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
	int Size()const;
};

void UFSet::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id) {
	if (m_far[id] == id)return id;
	return m_far[id] = Find(m_far[id]);
}

bool UFSet::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}

int UFSet::Size() const {
	return m_far.size();
}

template<typename T>
struct Edge {
	int u, v;
	T w;
};

template<typename T>
bool cmp(const Edge<T>& a,const Edge<T>& b) {
	return a.w < b.w;
}

template<typename T>
class Kruskal {
public:
	void Init(int maxId);
	void addEgde(int u, int v, T w);
	T Sovle();
private:
	UFSet m_uf;					//用这个来记录当前节点连通的集合
	vector<Edge<T>> m_edges;	//用于存放所有边的容器
};


template<typename T>
void Kruskal<T>::Init(int maxId) {
	m_uf.init(maxId);
	m_edges.clear();
}

template<typename T>
void Kruskal<T>::addEgde(int u, int v, T w) {
	Edge<T> edge{ u,v,w };
	m_edges.push_back(edge);
}

template<typename T>
T Kruskal<T>::Sovle() {
	T sum = 0;
	int edgeCount = 0;
	sort(m_edges.begin(), m_edges.end(), cmp<T>);
	for (int i = 0; i < m_edges.size(); i++) {
		Edge<T>& e = m_edges[i];
		if (m_uf.Union(e.u, e.v)) {		//如果它们在一个集合那说明已经连通了，否则没有连通就连通
			edgeCount++;
			sum += e.w;
		}
	}
	if (edgeCount < m_uf.Size() - 1) {	//最小生成树如果边数小于节点数-1机构不成最小生成树
		return -1;
	}
	return sum;
}

int main() {
	int n, m;
	cin >> n >> m;
	Kruskal<int>ks;
	ks.Init(n);
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		ks.addEgde(u, v, w);
	}
	int sum = ks.Sovle();
	if (sum == -1)cout << "orz" << endl;
	else cout << sum << endl;
	return 0;
}

九、经典例题

连通分量的个数

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSet {
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int>m_far;
};

void UFSet::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id) {		//递归查找这颗数的根结点
	if (m_far[id] == id)return id;
	return m_far[id] = Find(m_far[id]);
}

bool UFSet::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}


int main() {
	int n, m;
	cin >> n >> m;
	UFSet uf;
	uf.init(n);
	int cnt = n;
	while (m--) {
		int u, v;
		cin >> u >> v;
		if (uf.Union(u, v)) {
			cnt--;
		}
	}
	cout << cnt << endl;
	return 0;
}

不能超过3

#include<iostream>
#include<unordered_map>
using namespace std;

class UFSet {
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int>m_far;
};

void UFSet::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id) {		//递归查找这颗数的根结点
	if (m_far[id] == id)return id;
	return m_far[id] = Find(m_far[id]);
}

bool UFSet::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}


int main() {
	int n, m;
	cin >> n >> m;
	UFSet uf;
	uf.init(n);
	int cnt = n;
	while (m--) {
		int u, v;
		cin >> u >> v;
		if (uf.Union(u, v)) {
			cnt--;
		}
	}
	cout << cnt << endl;
	return 0;
}

修建公路1

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

class UFSet {
private:
	unordered_map<int, int>m_far;
public:
	void init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
	int Size()const;
};

void UFSet::init(int maxId) {
	m_far.clear();
	for (int i = 1; i <= maxId; i++) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id) {
	if (m_far[id] == id)return id;
	return m_far[id] = Find(m_far[id]);
}

bool UFSet::Union(int id1, int id2) {
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2)return false;
	m_far[s1] = s2;
	return true;
}

int UFSet::Size() const {
	return m_far.size();
}

template<typename T>
struct Edge {
	int u, v;
	T w;
};

template<typename T>
bool cmp(const Edge<T>& a,const Edge<T>& b) {
	return a.w < b.w;
}

template<typename T>
class Kruskal {
public:
	void Init(int maxId);
	void addEgde(int u, int v, T w);
	T Sovle();
private:
	UFSet m_uf;					//用这个来记录当前节点连通的集合
	vector<Edge<T>> m_edges;	//用于存放所有边的容器
};


template<typename T>
void Kruskal<T>::Init(int maxId) {
	m_uf.init(maxId);
	m_edges.clear();
}

template<typename T>
void Kruskal<T>::addEgde(int u, int v, T w) {
	Edge<T> edge{ u,v,w };
	m_edges.push_back(edge);
}

template<typename T>
T Kruskal<T>::Sovle() {
	T sum = 0;
	int edgeCount = 0;
	sort(m_edges.begin(), m_edges.end(), cmp<T>);
	for (int i = 0; i < m_edges.size(); i++) {
		Edge<T>& e = m_edges[i];
		if (m_uf.Union(e.u, e.v)) {		//如果它们在一个集合那说明已经连通了，否则没有连通就连通
			edgeCount++;
			sum += e.w;
		}
	}
	if (edgeCount < m_uf.Size() - 1) {	//最小生成树如果边数小于节点数-1机构不成最小生成树
		return -1;
	}
	return sum;
}

int main() {
	int n, m;
	cin >> n >> m;
	Kruskal<long long>ks;
	ks.Init(n);
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		ks.addEgde(u, v, w);
	}
	long long sum = ks.Sovle();
	cout << sum << endl;
	return 0;
}

十、总结与学习建议

1. 核心总结
• 并查集的核心是通过树形结构和优化技术实现高效的集合管理。
• 高阶问题的突破口通常在于带权并查集或动态并查集。
2. 学习建议
• 分类刷题：按问题类型集中练习（如连通性问题、动态连通性、分组问题）。
• 理解优化技术：掌握路径压缩和按秩合并的原理与实现。
• 手写模拟过程：在纸上画出树形结构，加深直观理解。

在这里插入图片描述

希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布