C++实现并查集

本文实例为大家分享了C++实现并查集的具体代码，供大家参考，具体内容如下

#include 
#include 
#include 

using namespace std;

class UnionFind{
private:
  vector parent;
  int count;
  //优化，记录p和q所在组的深度，在合并时将深度小的结点的根指向深度大的结点的根
  vector 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 

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

同时谢谢这位作者的分享
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。