@[美玉无瑕](/space/show?uid=89948) 这玩意叫并查集Union Set。。。
by Nero_Claudius @ 2018-07-21 19:57:36
还有判断是否有共同祖先这样不就行了吗：
```cpp
int find(int x){return (x==f[x])?x:f[x]=find(f[x])}
if(find(x)==find(y))cout<<"Y\n";
cout<<"N\n";
```
by Nero_Claudius @ 2018-07-21 20:00:06
@[DARTH_VADER](/space/show?uid=38859) 大佬我们交朋友把
by 御·Dragon @ 2018-07-21 20:02:12
而且并查集肯定是路径压缩啊
by Taduro @ 2018-07-21 20:09:41
%%%大佬都学到并查列了，我才学到动态划分
by kitakami @ 2018-07-21 20:14:04
@[多弗桃](/space/show?uid=63661) 按秩合并教你做人（可持久化的毒瘤卡空间）
by AThousandSuns @ 2018-07-21 20:14:28
@[DARTH_VADER](/space/show?uid=38859) @[多弗桃](/space/show?uid=63661) @[AThousandSuns](/space/show?uid=72118)
求助！
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
struct Node{
int father;
int d;
}s[MAXN];
int n,m,z,x,y,k;
int dg(int p,int o){
if(s[p].father==o)return 1;
if(s[p].father!=s[p].d){
p=s[p].father;
dg(p,o);
}
if(s[p].father==s[p].d)return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
s[i].d=i;
}
for(int i=1;i<=m;i++){
scanf("%d",&z);
scanf("%d %d",&x,&y);
switch(z){
case 1:{
s[y].father=x;
break;
}
case 2:{
if(dg(y,x))printf("Y\n");
else printf("N\n");
break;
}
}
}
return 0;
}
```
by 御·Dragon @ 2018-07-21 20:17:25
@[DARTH_VADER](/space/show?uid=38859) @[多弗桃](/space/show?uid=63661) @[萝莉大法好](/space/show?uid=56251) @[AThousandSuns](/space/show?uid=72118)
改了一下，再次求助
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20010;
int s[MAXN];
int n,m,z,x,y,k;
int fin(int p){
if(s[p]==0)return p;
fin(s[p]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d",&z);
scanf("%d %d",&x,&y);
switch(z){
case 1:{
s[y]=x;
break;
}
case 2:{
if(fin(y)==fin(x))printf("Y\n");
else printf("N\n");
}
}
}
return 0;
}
//样例过了，但10分
```
by 御·Dragon @ 2018-07-22 10:21:12
@[封禁用户名f8617dda](/space/show?uid=37682) 本人AC代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10010;
int n,m,z,x,y;
struct Unionset{
private:
int f[N];
public:
Unionset(){
for(int i=1;i<=n;i++)f[i]=i;
}
int find(int x){if(x==f[x])return x;return f[x]=find(f[x]);}
void merge(int x,int y){x=find(x),y=find(y);if(x!=f[y])f[y]=x;return;}
};
int main(){
cin>>n>>m;
Unionset U;
for(int i=0;i<m;i++){
cin>>z>>x>>y;
if(z==1)U.merge(x,y);
else{if(U.find(x)==U.find(y))cout<<"Y\n";else cout<<"N\n";}
}return 0;
}
```
by Nero_Claudius @ 2018-07-22 10:31:16
@[DARTH_VADER](/space/show?uid=38859) 当然感谢你的好意，但是只要求用本人的超烂算法搞懂就行了。谢谢！
by 御·Dragon @ 2018-07-22 10:34:38