daily pastebin goal
31%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # disjoint_set
  2. ## pattern1
  3.  
  4. ```cpp
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7.  
  8. struct disjoint_set{
  9.   long parent[1<<17];
  10.   long rank[1<<17];
  11.   disjoint_set(long n){
  12.     for(long i=0;i<n;i++){
  13.       parent[i]=i;
  14.       rank[i]=0;
  15.     }
  16.   }
  17.   long find(long x){
  18.     if(parent[x]==x)return x;
  19.     else return parent[x]=find(parent[x]);
  20.   }
  21.   bool unite(long x,long y){
  22.     x=find(x);
  23.     y=find(y);
  24.     if(x==y)return false;
  25.     if(rank[x]<rank[y])parent[x]=y;
  26.     else{
  27.       parent[y]=x;
  28.       if(rank[x]==rank[y])rank[x]++;
  29.     }
  30.     return true;
  31.   }
  32.   bool is_same(long x,long y){return find(x)==find(y);}
  33. };
  34.  
  35. int main(void){
  36.   disjoint_set ds(100);
  37.   ds.unite(0,1);
  38.   ds.unite(2,3);
  39.   cout<<ds.is_same(0,1)<<endl;
  40.   cout<<ds.is_same(0,2)<<endl;
  41.   return 0;
  42. }
  43. ```
  44.  
  45. ## pattern2
  46. こちらは各集合の要素数も取得できる
  47.  
  48. ```cpp
  49. #include<bits/stdc++.h>
  50. using namespace std;
  51.  
  52. struct disjoint_set{
  53.   vector<long>data;
  54.   disjoint_set(long size){data.assign(size, -1);}
  55.   bool merge(long x,long y){
  56.     x=root(x),y=root(y);
  57.     if(x==y)return false;
  58.     if(data[x]>data[y])swap(x, y);
  59.     data[x]+=data[y];
  60.     data[y]=x;
  61.     return true;
  62.   }
  63.   long root(long k){
  64.     if(data[k]<0)return k;
  65.     return data[k]=root(data[k]);
  66.   }
  67.   bool same(long x,long y){return root(x)==root(y);}
  68.   long size(long k){
  69.     return -data[root(k)];
  70.   }
  71. };
  72.  
  73. int main(){
  74.   disjoint_set ds(100);
  75.   ds.merge(0,1);
  76.   ds.merge(2,3);
  77.   cout<<ds.same(0,1)<<endl;
  78.   cout<<ds.same(0,2)<<endl;
  79.   cout<<ds.size(2)<<endl;
  80.   return 0;
  81. }
  82. ```
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top