给出一个并查集,请完成合并和查询操作。
输入格式:
第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Z*i、Xi、Yi*。
当Z**i=1时,将X*i与Y*i所在的集合合并。
当Z**i=2时,输出X*i与Y*i是否在同一集合内,是的话输出Y;否则的话输出N。
输出格式:
对于每一个Z**i=2的操作,对应一行输出,每行包含一个大写字母,为Y或者N。
输入样例:
1 2 3 4 5 6 7 8
| 4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
|
输出样例:
数据规模:
对于30%的数据,N<=10,M<=20;
对于70%的数据,N<=100,M<=1000;
对于100%的数据,N<=10000,M<=200000。
思路:
该题为模板题目,主要有两步
1)合并 merge
2)查找 find
注意:该题需要路径压缩
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #include<bits/stdc++.h> using namespace std; #define MAX 200006 typedef long long ll; int n,m,i,p[MAX/2]; int a[MAX],b[MAX],c; void init(int n) { for(i=1; i<=n; i++) p[i]=i; } int find(int x) { if(p[x]!=x) return p[x]=find(p[x]); return x; } void merge(int a,int b) { int x=find(a); int y=find(b); if(x!=y) p[x]=y; } int main() { scanf("%d%d",&n,&m); init(n); for(i=1; i<=m; i++) { scanf("%d%d%d",&c,&a[i],&b[i]); if(c==1) merge(a[i],b[i]); else if(c==2) { if(find(a[i])!=find(b[i])) cout<<"N"<<endl; else cout<<"Y"<<endl; } } return 0; }
|