题目描述
感觉并查集是一个很神奇的算法
代码如下 过程就类似收小弟一样233~~~
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//很巧妙的一个算法
int f[10005],n,m;
int find(int x){if(x==f[x]) return x;//查找老大 找出最终老大 f[x]=find(f[x]);return f[x];
}
void merge(int x,int y){int b=find(x);int c=find(y);if(b!=c){//如果不是小弟 收! f[c]=f[b];} return ;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;for(int i=0;i<m;i++){int b,c,flag;cin>>flag>>b>>c;if(flag==1){merge(b,c);//合并操作可以看作是b或者c收小弟 }else if(flag==2){if(find(b)==find(c)) cout<<"Y"<<endl;else cout<<"N"<<endl;}}return 0;
}