并查集模板

 1 #include<bits/stdc++.h>//万能头文件 
 2 using namespace std;
 3 
 4 const int maxn=1010;
 5 int fa[maxn];
 6 
 7 void init(){
 8     int n=1000;
 9     for(int i=1;i<=n;i++){
10         fa[i]=i;
11     }    
12 }//赋初值 
13 
14 int find(int x){
15     return x==fa[x]? x : fa[x]=find(fa[x]);
16 }//寻找祖先节点  
17 
18 void baba(int x,int y){
19     int fx = find(x);
20     int fy = find(y);
21     fa[fx] = fy;
22 }//交朋友
23 
24 int size[1000]={0};
25 for(int i=1;i<=n;i++){
26     size[find(i)]++;
27 }//计算每个祖宗节点团体内有几个人 
28 
29 int main(){
30     init();//初始化 
31     int a,x,y;
32     while(scanf("%d %d %d",&a,&x,&y)){
33         if(a==1){
34             baba(x,y);
35         }
36         else{
37             if(find(x)!=find(y)) printf("NO\n");
38             else printf("YES\n");
39         }
40     }
41     return 0;
42 }

 1 //未优化并查集
 2 
 3 #include<vector>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 class DisjSet{
 8     private:
 9         std::vector<int> parent;
10         
11     public:
12         DisjSet(int max_size) : parent(std::vector<int>(max_size)){
13             for(int i=0;i<max_size;++i)
14                 parent[i] = i;
15         }
16         
17         int find(int x){
18             return parent[x]==x? x : find(parent[x]);
19         }
20             
21         void to_union(int x,int y){
22             parent[find(x)] == find(x2);
23         }
24         
25         bool is_same(int x,int y){
26             return find(x) == find(y);
27         }
28 };

 1 //并查集的优化
 2 
 3 //一：按秩合并 
 4 //    用“秩”(rank)代替高度，秩表示高度的上界，通常情况我们令只有一个节点的树的秩为0。
 5 //    两棵秩分别为r1、r2的树合并，如果秩不相等，我们将秩小的树合并到秩大的树上，
 6 //    这样就能保证新树秩不大于原来的任意一棵树。如果r1与r2相等，两棵树任意合并，并令新树的秩为r1 + 1。 
 7     
 8 //二：路径压缩
 9 //    在执行Find的过程中，将路径上的所有节点都直接连接到根节点上。 
10 
11 #include<vector>
12 class DisjSet{
13     private:
14         std::vector<int>parent;
15         std::vector<int>rank;//秩
16         
17     public:
18         DisjSet(int max_size) : parent(std::vector<int>(max_size)),
19                                 rank(std::vector<int>(max_size,0)){
20             for(int i=0;i<max_size;i++)
21                 parent[i] = i;                    
22         } 
23         
24         int find(int x){
25             return x == parent[x]? x : (parent[x] = find(parent[x]));
26         }
27         
28         void to_union(int x,int y){
29             int fx = find(x);
30             int fy = find(y);
31             if(rank[fx] > rank[fy])
32                 parent[fy] = fx;
33             else{
34                 parent[fx] = fy;
35                 if(rank[fx] == rank[fy])
36                     rank[fy]++;
37             }
38         }
39         bool is_same(int x,int y){
40             return find(x) == find(y);
41         }
42 };