并查集

如果有一个关系网，我们需要建立两点之间的关系，如果仅用一维链表 ，则有可能无法考虑到两点同为一点 “儿子”的 情况，则 我们需要建立一个方式，从而直接对比两点“祖父”。

一 .递归查询

int find(int x){
　　if(fa[x]==x)return x;//只有祖父自环，如果他也自环，则找到父节点
　　return find(fa[x]);//不然往父节点继续靠近
}

二.合并两节点

void add(int xx,int yy){
　　int fa_xx=find(xx);
　　int fa_yy=find(yy);
　　fa[fa_xx]=fa_yy;//将两者合并
}

以上为基础并查集，记得要初始化：在每一个数在建立关系前与自己自环.

现在我们可以开始想想大样例该如何过了。

加如题目告诉你 1-7，7-3，3-4，5-6，2-6，1-2，然后询问你5，4是否有关系，按原本方法可得画图：

 根据树形图可知；两者都是1的子孙，但是查询次数多，如果更大的数据可能会爆，所以我们可以考虑在每一次更新后将点值更新为祖先值。

 如此反复跟新，便可以将速度大为优化，代码中优化也很简单 

int find(int x){
　　if(fa[x]==x)return x;//只有祖父自环，如果他也自环，则找到父节点

　　fa[x]=find(fa[x]);//每次更新点值
　　return fa[x];//不然往父节点继续靠近
}

如此这般 便完成优化了。

三.例题试炼

1.P1551 亲戚 

简单模板，直接调用即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,p,t[100000]; int a,b;
 4 int find(int x){
 5     if(t[x]==x)return x;
 6     return t[x]=find(t[x]);
 7 }
 8 void add(int x,int y){
 9     int fa_x=find(x);
10     int fa_y=find(y);
11     t[fa_x]=fa_y;
12 }
13 int main(){
14     
15     cin>>n>>m>>p;
16     for(int i=1;i<=n;i++)t[i]=i;
17     for(int i=1;i<=m;i++){
18         cin>>a>>b;
19         add(a,b);
20     }
21     for(int i=1;i<=p;i++){
22         cin>>a>>b;
23         if(find(a)==find(b))cout<<"Yes"<<endl;
24         else cout<<"No"<<endl;
25     }
26     
27     return 0;
28 }

2.P3367 【模板】并查集

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,z,x,y;
 4 int a[10010];
 5 int find(int q){
 6     if(a[q]==q)return q;
 7     return a[q]=find(a[q]);
 8 }
 9 int main(){    
10     cin>>n>>m;
11     for(int i=1;i<=n;i++)a[i]=i;
12     for(int i=1;i<=m;i++){
13         cin>>z>>x>>y;
14         if(z==1){
15             a[find(x)]=find(y);
16             
17         }else{
18             if(find(x)==find(y))cout<<"Y"<<endl;
19             else cout<<"N"<<endl;
20         }
21     }
22      
23 
24 return 0;
25 }