并查集的操作:
1.将两点所在的集合合并
2.询问两点是否在同一集合内
这种实现方法让人有种树的感觉。。。
||(f[i])表示(i)的父亲结点||初始化(f[i]=i)即自己属于自己的集合||
那么我们将一个集合的“代表”(也可以理解为祖先)的父亲设为另一个集合的“代表”(祖先),就可以达到集合合并的效果。
但是如果不进行优化,那么这棵树的深度可能会变得很大,频繁找祖先就十分耗时间复杂度。 于是我们有个优化:在找祖先的过程中,直接把非根结点的父亲设为根节点。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m;
#define MAXN 10000
int f[MAXN+1];
int find(int x)
{
if (f[x]==x) return x;
return f[x]=find(f[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
f[i]=i;
}
for (int i=1,z,x,y;i<=m;i++)
{
scanf("%d%d%d",&z,&x,&y);
if (z==1)
{
f[find(f[x])]=find(y);
continue;
}
if (find(x)==find(y))
{
printf("Y
");
continue;
}
printf("N
");
}
return 0;
}