C++是如何实现并查集的-创新互联

创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商，新人活动买多久送多久，划算不套路！

小编给大家分享一下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;
    }
  }
};