C++如何实现并查集 C++并查集的数据结构与实现

并查集是一种高效的集合合并与查询数据结构，主要用于判断元素是否属于同一集合或进行集合合并。其核心操作包括：1. makeset(x)创建包含元素x的集合；2. find(x)查找x所属集合的代表；3. union(x, y)合并x和y所在的集合。实现上使用数组存储父节点和秩，初始化时每个元素自成一集合，通过路径压缩和按秩合并优化性能，使时间复杂度接近o(α(n))。应用于图论中可判断连通性、检测环、构建最小生成树等。相比哈希表，并查集在动态集合合并效率更高，但不支持直接删除元素。

C++实现并查集，本质上就是解决集合的合并与查询问题，用来判断元素是否属于同一集合，或者将两个集合合并成一个。核心在于用树形结构表示集合，并利用路径压缩和按秩合并等技巧优化性能。

解决方案

并查集，也叫作不相交集合数据结构，主要操作包括：

1. MakeSet(x)：创建一个新的集合，其中包含元素x。x是这个集合的代表。
2. Find(x)：查找元素x所属的集合的代表。
3. Union(x, y)：将包含元素x和元素y的集合合并成一个集合。

C++实现通常使用数组来表示每个元素的父节点，初始化时每个元素的父节点指向自己，表示各自独立的集合。

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;
class DisjointSet {
public:
DisjointSet(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) {
parent[i] = i; // 初始化每个元素的父节点指向自己
}
}
// 查找元素x所属集合的代表（带路径压缩）
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // 路径压缩：将x的父节点直接指向根节点
}
return parent[x];
}
// 合并包含元素x和元素y的集合（按秩合并）
void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++; // 如果秩相同，则将其中一个树的秩增加1
}
}
}
private:
vector<int> parent; // 存储每个元素的父节点
vector<int> rank;   // 存储每个集合的秩（树的高度的一个上界）
};
int main() {
DisjointSet ds(10); // 创建一个包含10个元素的并查集
ds.Union(0, 1);
ds.Union(2, 3);
ds.Union(4, 5);
ds.Union(0, 2); // 将包含0和2的集合合并
cout << "Find(0) = " << ds.Find(0) << endl; // 应该和Find(2)相同
cout << "Find(2) = " << ds.Find(2) << endl;
cout << "Find(1) = " << ds.Find(1) << endl; // 应该和Find(0), Find(2)相同
cout << "Find(4) = " << ds.Find(4) << endl;
cout << "Find(5) = " << ds.Find(5) << endl;
return 0;
}

并查集在图论中的应用有哪些？

并查集在图论中用途广泛，最经典的应用之一是判断图的连通性。例如，可以用并查集来检测图中是否存在环。如果在一个无向图中，每次添加一条边，如果边的两个顶点已经在同一个集合中，那么就形成了环。此外，Kruskal算法中，也用并查集来判断加入的边是否会形成环，以此来构建最小生成树。还可以用来解决迷宫生成、社交网络分析等问题，核心在于维护节点之间的连通关系。

如何优化并查集的性能？

优化并查集性能的关键在于路径压缩和按秩合并。路径压缩是在Find操作时，将查找路径上的每个节点的父节点直接指向根节点，从而降低树的高度，减少后续查找的时间复杂度。按秩合并是在Union操作时，将秩较小的树合并到秩较大的树上，秩可以简单理解为树的高度。这样可以避免树的高度增长过快，保持树的平衡。通过这两种优化，并查集的平均时间复杂度可以接近O(α(n))，其中α(n)是反阿克曼函数，增长非常缓慢，可以认为是一个常数。

并查集与其他的集合数据结构（如哈希表）相比，有什么优缺点？

并查集专注于解决集合的合并与查询问题，特别是判断两个元素是否属于同一集合。与哈希表相比，并查集在处理动态集合合并方面更高效。哈希表适合于快速查找某个元素是否存在于集合中，但合并两个集合需要遍历其中一个集合的所有元素，效率较低。并查集的优点是实现简单，空间复杂度较低，查询和合并操作的平均时间复杂度接近常数级别。缺点是不能直接删除集合中的元素，因为删除操作会破坏树形结构。选择哪种数据结构取决于具体的应用场景和需求。如果需要频繁地合并集合，并查集是更合适的选择。