# include "cstdio"
# include "iostream"
```cpp
using namespace std;
int f[10005];
int find(int i)
{
if(f[i]!=i)f[i]=find(f[i]);
return f[i];
}
void join(int x,int y)
{
if(find(x)!=find(y))f[find(f[x])]=find(y);
}
int main()
{
int n,m,x,y,z;
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
cin>>z>>y>>x;
if(z==1)
join(y,x);
else
if(find(y)==find(x))
cout<<'Y'<<endl;
else
cout<<'N'<<endl;
}
return 0;
}
```
by lydon @ 2017-06-15 20:56:13
```cpp
#include<bits/stdc++.h>
using namespace std;
int f[10001],n,m,zi,xi,yi;
int getf(int x)
{
if(f[x]==x) return x;//f[x]最后为根节点
else
{f[x]=getf(f[x]);//压缩路径，把路过的点付值，提高速度
return f[x];
}
}
void add(int x,int y)
{ int t1,t2;
t1=getf(x);
t2=getf(y);
if(t1!=t2)
f[t2]=t1;//如果不是同一祖先，t2合并到t1内
return;
}
void ch(int x,int y)
{ int a1,a2;
a1=getf(x);
a2=getf(y);
if(a1==a2) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
cin>>zi>>xi>>yi;
if(zi==1)
add(xi,yi);
if(zi==2)
ch(xi,yi);
}
}
```
by 一念之间 @ 2017-07-16 20:28:17
合并应该是x所在的并查集和y所在的并查集合并，是把一个root合并到另一个root上，不是直接fa[x]=y
by QRcode @ 2017-07-27 14:48:12
楼上说话一点用都没有
by 早右昕 @ 2017-07-28 15:40:26
每次询问都需要给出应答，但是你的最外层if中r1!=r2会减少一些应答
by wzhhahah @ 2017-08-04 16:43:58
不对是增多一些多余的应答
by wzhhahah @ 2017-08-04 16:45:14