题目链接:https://www.luogu.org/problemnew/show/3367
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,x,y,z,fa[200010];
int get(int a)
{
if(fa[a]==a)
return a;
else return fa[a]=get(fa[a]);
}
int main()
{
int fxx,fxy;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
fa[i]=i;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&z,&x,&y);
fxx=get(x);
fxy=get(y);
if(z==1)
{
fa[fxx]=fxy;
}
else
{
if(fxx==fxy)
printf("Y\n");
else
printf("N\n");
}
}
return 0;
}
并查集也称为不相交集数据结构。
此算法的发展经历了十多年,其中Robert E.Tarjan做出了很大的贡献。此前,John E.Hoperoft和Jeffrey D.Ullman也进行了大量的分析。
并查集通过一维数组实现,其本质是维护一个森林。
略略略
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)