創(chuàng)新互聯(lián)www.cdcxhl.cn八線動態(tài)BGP香港云服務器提供商，新人活動買多久送多久，劃算不套路！

創(chuàng)新互聯(lián)是一家專注于成都做網站、網站制作與策劃設計,孫吳網站建設哪家好?創(chuàng)新互聯(lián)做網站,專注于網站建設10余年,網設計領域的專業(yè)建站公司;建站業(yè)務涵蓋:孫吳等地區(qū)。孫吳做網站價格咨詢:028-86922220

小編給大家分享一下C++是如何實現(xiàn)并查集的，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

#include 
#include 
#include 

using namespace std;

class UnionFind{
private:
  vector parent;
  int count;
  //優(yōu)化，記錄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;
    }
  }
};

新聞標題：C++是如何實現(xiàn)并查集的-創(chuàng)新互聯(lián)
轉載來于：http://weahome.cn/article/dhpodh.html