• API
• FAQ
• Tools
• Archive
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.

Top