C++ 手写代码：实现并查集完整教程

以下是一个简单的C++并查集实现： ```cpp #include <vector> #include <algorithm> class UnionFind { private: std::vector<int> p, rank; public: UnionFind(int n) : p(n), rank(n, 0) { for(int i = 0; i < n; ++i) p[i] = i; } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(rank[x] < rank[y]) std::swap(x, y); p[y] = x; if(rank[x] == rank[y]) ++rank[x]; } bool same(int x, int y) { return find(x) == find(y); } }; ``` 在这个实现中，我们使用了两个向量，`p`和`rank`。`p`用于存储每个元素的父节点，`rank`用于存储每个树的大小。`find`函数用于查找一个元素的根节点，`unite`函数用于合并两个树，`same`函数用于判断两个元素是否在同一个树中。 ######[AI写代码神器 | 274点数解答 | 2023-11-09 00:48:48]