C++实现并查集

本文实例为大家分享了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();
}

同时谢谢这位作者的分享

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。