C++ implements and checks the set
- 2020-10-23 20:14:53
- OfStack
Example of this article for you to share C++ implementation and check the set of specific code, for your reference, the specific content is as follows
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
class UnionFind{
private:
vector<int> parent;
int count;
// Optimize, record p and q The depth of the group in which the root of the node with a small depth is pointed to the root of the node with a large depth during the merge
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();
}
// Path to the compression
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{
// Of the two rank equal
parent[pRoot] = qRoot;
rank[qRoot] += 1;
}
}
};
This site to add 1 section of code, before the collection of 1 section of code:
#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();
}
And thanks to the author for sharing