题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入输出格式
输入格式:
第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N
输出格式:
如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N
代码:
1 #include<iostream>
2 using namespace std;
3 int n, m;
4 int par[10010];
5 int getpar(int x){
6 if(par[x]!=x) par[x] = getpar(par[x]);
7 return par[x];
8 }
9 void merge(int x, int y){
10 if(getpar(x) == getpar(y))
11 return;
12 par[getpar(x)] = getpar(y);
13 }
14 int query(int x, int y){
15 return getpar(x)==getpar(y);
16 }
17 int main(){
18 cin>>n>>m;
19 int i;
20 for(i = 1; i <= n; i++)
21 par[i] = i;
22 for(i = 1; i <= m; i++){
23 int z, x, y;
24 cin>>z>>x>>y;
25 if(z == 1){
26 merge(x, y);
27 }
28 else if(z == 2){
29 if(query(x,y))
30 cout<<"Y"<<endl;
31 else cout<<"N"<<endl;
32 }
33 }
34 return 0;
35 }
备注:
本来自己写了一遍,然后只得了20分orz
标黄的两行注意一下。
我要去刚Kruscal了。。
转载于:https://www.cnblogs.com/fangziyuan/p/6024270.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)