题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式
第一行包含两个整数N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行,每行包含三个整数 Zi,Xi,Yi 。
当 Zi=1 时,将 Xi 与 Yi 所在的集合合并。
当 Zi=2 时,输出 Xi 与 Yi 是否在同一集合内,是的输出 Y
;否则输出 N
。
输出格式
对于每一个 Zi=2 的操作,都有一行输出,每行包含一个大写字母,为 Y
或者 N
。
输入输出样例
输入 #1复制
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
Y
N
Y
说明/提示
对于 30% 的数据,N≤10,M≤20。
对于 70% 的数据,N≤100,M≤10^3。
对于 100% 的数据,1≤N≤10^4,1≤M≤2×10^5,1≤Xi,Yi≤N,Zi∈{1,2}。
嗯,这是个并查集的模板题。
首先,我们要知道何为并查集,我们可以这样理解,目前常用的是用树来解决问题,就是把一些节点连接起来,让他们有且仅有一个根节点,而我们要判断某些数是否在同一个集合——即同一个树——之中,那么我们可以找出它们的根节点,如果根节点相同,那么一定是在同一个集合中。
以此我们可以得出以下的函数:
int findi(int x)
{
if(pre[x]==x)
return x;
return pre[x]=findi(pre[x]);
}
这个函数就是用来找寻节点x的根节点,因为我们会在最开始给pre数组初始化,嗯……还是把总的代码贴出来吧。
#include <iostream>
#include <cstring>
using namespace std;
int pre[10000];
int findi(int x)
{
if(pre[x]==x)
return x;
return pre[x]=findi(pre[x]);
}
int main()
{
int n,m,z,x,y;
cin >>n>>m;
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=0;i<m;i++)
{
cin >>z>>x>>y;
if(z==1)
pre[findi(y)]=findi(x);
else {
if(findi(x)==findi(y))
cout <<"Y\n";
else cout <<"N\n";
}
}
}
我们在最开始会给pre数组赋初值,每个下标里的元素即使那个下标的量,那么这个定义在fini函数中就彰显出作用了,你想,如果一个节点的根节点就是他自己,是不是就代表着它就是根节点了。如果它本身并不是根节点,那我们可以一步步往父节点去找,直到找到根节点为之。其中的pre[x]=fini(pre[x]);是一种优化的做法,使得下次运用到x节点,x节点里的值就直接是它的根节点了,这样可以减少时间复杂度。
嗯,没了,完结撒花。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)