c++并查集

<think>好的，用户想要查找关于C++实现并查集的数据结构的资料或教程，还希望有示例代码。我需要先回忆并查集的基本概念和常见实现方式。并查集主要用于处理不相交集合的合并与查询问题，常见操作有查找根节点和合并两个集合。 用户提供的引用中有提到并查集的实现思路，比如引用[2]提到增加一个数组存储节点到父节点的权值，还有路径压缩和按秩合并的优化方法。引用[3]则提到使用前需要明确合并规则和查询需求，初始化时要确定集合大小，合并前先查询是否属于不同集合。这些信息可以作为参考。 首先，我应该解释并查集的基本结构，包括父节点数组和秩数组。然后分步骤讲解初始化、查找和合并操作。查找操作需要路径压缩，合并操作需要按秩合并，这两个优化能提高效率。接着给出一个基础的C++实现示例，包括类的定义和相关方法。 然后，考虑到用户可能需要更高级的功能，比如带权并查集，可以基于引用[2]提到的增加权值数组，解释如何扩展实现。这部分需要说明权值的含义和在查找、合并时的处理方式，确保权值正确更新。 最后，生成相关问题，帮助用户进一步学习，比如优化方法、时间复杂度、应用场景等。这些需要结合引用中的信息，确保问题相关且有深度。 需要注意的是，代码示例要符合C++语法，正确使用路径压缩和按秩合并，注释清晰。同时，引用用户提供的资料时要正确标注引用标记，比如路径压缩的部分引用[2]，注意事项引用[3]。 检查是否有遗漏的部分，比如并查集的应用场景，或者常见错误，比如忘记初始化父数组等。确保回答结构清晰，步骤明确，代码正确，示例易懂。</think>以下是为您整理的C++并查集数据结构实现详解： ### 一、并查集基础实现 #### 1.1 数据结构定义 基础并查集包含两个核心数组： - $parent[]$ 存储每个元素的父节点 - $rank[]$ 存储集合的秩（用于优化合并操作） ```cpp class UnionFind { private: vector<int> parent; vector<int> rank; public: UnionFind(int size) { parent.resize(size); rank.resize(size, 0); // 初始化每个元素的父节点为自身 for(int i = 0; i < size; ++i) parent[i] = i; } }; ``` #### 1.2 核心操作实现 **查找操作（带路径压缩）**： ```cpp int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩优化[^2] return parent[x]; } ``` **合并操作（按秩合并）**： ```cpp void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { // 属于不同集合时才合并[^3] if (rank[rootX] > rank[rootY]) parent[rootY] = rootX; else { parent[rootX] = rootY; if (rank[rootX] == rank[rootY]) rank[rootY]++; } } } ``` ### 二、带权并查集扩展 基于引用[2]的权值存储思路，增加权值数组： ```cpp class WeightedUnionFind { private: vector<int> parent; vector<int> weight; // 存储到父节点的权值 public: WeightedUnionFind(int size) { parent.resize(size); weight.resize(size, 0); for(int i=0; i<size; ++i) parent[i] = i; } int find(int x) { if(parent[x] != x) { int orig_parent = parent[x]; parent[x] = find(parent[x]); weight[x] += weight[orig_parent]; // 权值更新 } return parent[x]; } void unite(int x, int y, int value) { int rootX = find(x); int rootY = find(y); if(rootX != rootY) { parent[rootX] = rootY; weight[rootX] = value - weight[x] + weight[y]; } } }; ``` ### 三、应用场景 1. 图的连通性判断 2. 最小生成树算法（Kruskal算法） 3. 动态连接问题 4. 社交网络好友关系维护