本文实例为大家分享了C++实现并查集的具体代码，供大家参考，具体内容如下
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
class UnionFind{
private:
vector<int> parent;
int count;
//优化，记录p和q所在组的深度，在合并时将深度小的结点的根指向深度大的结点的根
vector<int> rank;
public:
UnionFind(int count){
parent.resize(count);
rank.resize(count);
this->count = count;
for(int i = 0; i < count; ++i){
parent[i] = i;
rank[i] = 1;
}
}
~UnionFind(){
parent.clear();
rank.clear();
}
//路径压缩
int find(int p){
assert(p >= 0 && p < count);
if(p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
bool isConnected(int p, int q){
return find(p) == find(q);
}
void unionElement(int p, int q){
int pRoot = find(p), qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot;
else if(rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{
//两者的rank相等
parent[pRoot] = qRoot;
rank[qRoot] += 1;
}
}
};
小编再补充一段代码，之前收藏的一段代码：
#include <iostream>
using namespace std;
class UF {
//cnt is the number of disjoint sets.
//id is an array that records distinct identity of each set,when two sets are merged ,their id will be same.
//sz is an array that records the child number of each set including the set self.
int *id, cnt, *sz;
public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
cnt = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i<N; i++) {
id[i] = i;
sz[i] = 1;
}
}
~UF() {
delete[] id;
delete[] sz;
}
// Return the id of component corresponding to object p.
int find(int p) {
if (p != id[p]){
id[p] = find(id[p]);
}
return id[p];
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) return;
// make smaller root point to larger one
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
}
else {
id[j] = i;
sz[i] += sz[j];
}
cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) {
return find(x) == find(y);
}
// Return the number of disjoint sets.
int count() {
return cnt;
}
};
void main(){
UF test(5);
test.merge(2, 3);
test.merge(3, 4);
cout << test.find(4);
cout << test.count();
}
同时谢谢这位作者的分享
您可能感兴趣的文章:c++并查集优化（基于size和rank）c++初级并查集知识点总结C++并查集亲戚(Relations)算法实例C++利用map实现并查集