温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++是如何实现并查集的

发布时间:2020-07-06 10:24:35 来源:亿速云 阅读:163 作者:清晨 栏目:开发技术

小编给大家分享一下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&#63;
 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();
}

看完了这篇文章,相信你对C++是如何实现并查集的有了一定的了解,想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI