题解 P3367 【【模板】并查集】
Hatsune_Miku
2017-07-11 11:00:37
这种数据结构题还是封装起来用比较舒服（强迫症）。
没什么好说的，就是带路径压缩的并查集（不路径压缩会TLE）。
常用于Kruskal算法等。
```cpp
#include<cstdio>
using namespace std;
#define maxn 10000
struct UnionFindSet
{
int x,y,v;
int fat[maxn];
UnionFindSet()
{
for(int i=0;i<maxn;i++)
fat[i]=i;
x=y=v=0;
}
inline int father(int x)
{
if(fat[x]!=x)
fat[x]=father(fat[x]);
return fat[x];
}
inline void unionn(int x,int y)
{
int fa=father(x);
int fb=father(y);
if(fa!=fb)
fat[fa]=fb;
}
};
UnionFindSet s;
int n,m,z,x,y;
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d",&z,&x,&y);
if(z==1)
s.unionn(x,y);
else if(z==2)
{
if(s.father(x)!=s.father(y))
printf("N\n");
else
printf("Y\n");
}
}
return 0;
}
```