先上题目
题目描述 如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式 第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N
输出格式 如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N
思路
对于并查集总共有两个操作,1.添加联系,2.查询是否具有关系,可以类比成老大找小弟的关系,添加关系既某个人打过了另一个人,他就将另一个人收为小弟,但是,当某个人收了一个小弟后,小弟并不知道他的大哥还有大哥,这显然不合适,难以实现第二项操作,这时便可以引进一维数组f[i],表示第i个人的最大的老大是谁,可以定义一个函数fuc()来求他的最大的老大。
int fuc(int k) {
if (f[k] == k) return k;
return f[k] = fuc(f[k]);
}
接下来的两个需要实现的操作
1.添加联系
可令某个人的最大的老大的老大是另一个人的最大的老大相等即:
f[fuc(temp2)] = fuc(temp3);
2.查询是否具有关系
if(fuc(temp2) == fuc(temp3))
下面是完整代码:
#include<iostream>
using namespace std;
int n,m,f[10050];
int fuc(int k) {
if (f[k] == k) return k;
return f[k] = fuc(f[k]);
}
int main() {
cin>>n>>m;
for (int i=1;i<=n;i++) f[i] = i;
for (int i=1;i<=m;i++) {
int temp1,temp2,temp3;
cin>>temp1>>temp2>>temp3;
if (temp1 == 1 ) {
f[fuc(temp2)] = fuc(temp3);
}else {
if (fuc(temp2) == fuc(temp3)) {
cout<<"Y"<<endl;
}else {
cout<<"N"<<endl;
}
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)