并查集是一种高效的集合合并与查询数据结构，主要用于判断元素是否属于同一集合或进行集合合并。其核心操作包括：1. makeset(x)创建包含元素x的集合；2. find(x)查找x所属集合的代表；3. union(x, y)合并x和y所在的集合。实现上使用数组存储父节点和秩，初始化时每个元素自成一集合，通过路径压缩和按秩合并优化性能，使时间复杂度接近o(α(n))。应用于图论中可判断连通性、检测环、构建最小生成树等。相比哈希表，并查集在动态集合合并效率更高，但不支持直接删除元素。
C++实现并查集，本质上就是解决集合的合并与查询问题，用来判断元素是否属于同一集合，或者将两个集合合并成一个。核心在于用树形结构表示集合，并利用路径压缩和按秩合并等技巧优化性能。
解决方案
并查集，也叫作不相交集合数据结构，主要操作包括：
- MakeSet(x)：创建一个新的集合，其中包含元素x。x是这个集合的代表。
- Find(x)：查找元素x所属的集合的代表。
- Union(x, y)：将包含元素x和元素y的集合合并成一个集合。
C++实现通常使用数组来表示每个元素的父节点，初始化时每个元素的父节点指向自己，表示各自独立的集合。
立即学习“C++免费学习笔记（深入）”；
#include#include 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 parent; // 存储每个元素的父节点 vector 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)是反阿克曼函数，增长非常缓慢，可以认为是一个常数。
并查集与其他的集合数据结构（如哈希表）相比，有什么优缺点？
并查集专注于解决集合的合并与查询问题，特别是判断两个元素是否属于同一集合。与哈希表相比，并查集在处理动态集合合并方面更高效。哈希表适合于快速查找某个元素是否存在于集合中，但合并两个集合需要遍历其中一个集合的所有元素，效率较低。并查集的优点是实现简单，空间复杂度较低，查询和合并操作的平均时间复杂度接近常数级别。缺点是不能直接删除集合中的元素，因为删除操作会破坏树形结构。选择哪种数据结构取决于具体的应用场景和需求。如果需要频繁地合并集合，并查集是更合适的选择。
