7-36 并查集【模板】 (10 分)
给出一个并查集，请完成合并和查询操作。
输入格式:
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi。
当Zi=1时，将Xi与Yi所在的集合合并。
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则的话输出N。
输出格式:
对于每一个Zi=2的操作，对应一行输出，每行包含一个大写字母，为Y或者N。
输入样例:
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
结尾无空行
输出样例:
1. N 2. Y 3. N 4. Y
结尾无空行
数据规模:
对于30%的数据，N<=10，M<=20；
对于70%的数据，N<=100，M<=1000；
对于100%的数据，N<=10000，M<=200000。
#include<iostream> using namespace std; int n,m; int p[1000000]; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } void unite(int x,int y){ int fx=find(x); int fy=find(y); p[fx]=fy; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)p[i]=i; for(int i=0;i<m;i++){ int z,x,y; cin>>z>>x>>y; if(z==1)unite(x,y); else{ if(find(x)!=find(y))puts("N"); else puts("Y"); } } return 0; }
