并查集个人认为就是合并和查询集合的算法，根据名字和作用推出来的，说的比较高大上。我们在操作的时候采用数组来表示一个集合的祖先，分成合并，查找祖先两个过程。祖先也就是根节点，并查集的巧妙之处就在于每一个集合里的元素都是指向的集合的代表（也就是根节点，fa[x]）所以每次查找和改变的次数都可以很少。而将集合合并的时候就只要改变根节点的指向就行了，指向另一个集合的根节点。

下面是AC代码，仔细是十分好理解的。

 1 #include<bits/stdc++.h>
 2 using namespace std;    
 3 int n,m;
 4 int fa[10010];//存每个元素的父节点
 5 int get(int x){
 6     if (x==fa[x]) return x;//如果元素指向的是自己那就是根节点
 7     return fa[x] = get(fa[x]);//不是自己的话就继续向下找
 8 }
 9 void hebing(int x,int y){
10     fa[get(x)]=get(y);//改变根节点的指向，指向要合并的那个根节点
11 }
12 int main(){
13     cin>>n>>m;
14     for (int i=1;i<=n;i++) fa[i]=i;//一开始每一元素都是一个集合
15     for (int i=1;i<=m;i++){
16         int a,b,c;
17         cin>>a>>b>>c;
18         if (a==1) hebing(b,c);//合并集合
19         else {
20             if (get(b)==get(c))//判断是否在同一个集合内，也就是根节点是否相同
21             cout<<"Y"<<endl;
22             else cout<<"N"<<endl; 
23         }
24     }
25 }

 

版权声明：本文为fnbk原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fnbk/p/9320021.html