@[张小花](/space/show?uid=130639) 您确定您这是写的并查集。。。。感觉好乱qwq
by Null_Cat @ 2019-08-22 20:56:08
~~假并查集~~
by End_donkey @ 2019-08-22 20:56:40
@[张小花](/space/show?uid=130639) 为什么不试试路径压缩呐
by 0nullptr @ 2019-08-22 20:56:49
@[张小花](/space/show?uid=130639) w的AC代码：
```cpp
#include<cstdio>
#define re register
using namespace std;
int fP(int,int[]);
int main(){
int *n=new int;
int *m=new int;
scanf("%d%d",n,m);
int *p=new int[*n+1];
int *a=new int;
int *cmd=new int;
int *b=new int;
for(int i=1;i<=*n;i++) p[i]=i;
for(int i=1;i<=*m;i++){
scanf("%d%d%d",cmd,a,b);
if(*cmd==1){
p[fP(*a,p)]=fP(*b,p);
}
else if(*cmd==2){
if(fP(*a,p)==fP(*b,p)) putchar('Y');
else putchar('N');
putchar('\n');
}
}
delete n;
delete m;
delete cmd;
delete a;
delete b;
delete[] p;
return 0;
}
int fP(int a,int b[]){
if(a==b[a]) return a;
else return b[a]=fP(b[a],b);
}
```
其实并查集的话只需要把查询弄成函数就够了qwq
by Null_Cat @ 2019-08-22 20:57:20
这个并查集好草啊
一般不得把父结点在初始化时设为自己吗
by muyang_233 @ 2019-08-22 20:57:51
@[muyang_233](/space/show?uid=113521) 可以设-1的，只不过是设自己更常用。。。
by Null_Cat @ 2019-08-22 20:58:27
@[张小花](/space/show?uid=130639)
可能初始化有点问题
放下我的码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[10010];
int k,u,v;
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
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",&k,&u,&v);
if(k==1){
int fa1=find(u);
int fa2=find(v);
fa[fa1]=fa2;
}
else{
int fa1=find(u);
int fa2=find(v);
if(fa1==fa2) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
```
by End_donkey @ 2019-08-22 20:58:49
@[张小花](/space/show?uid=130639) 而且并查集不用树存储就行。。。只需要开一个parent数组存所在集合的代表元素即可qwq
by Null_Cat @ 2019-08-22 20:59:27
@[张小花](/space/show?uid=130639) 另外合并到那个都无所谓，所以个人感觉是因为多开了一个size的缘故，这个size其实根本不需要
by Null_Cat @ 2019-08-22 21:02:21
@[张小花](/space/show?uid=130639) 应该是$dfs$爆栈了
把
```cpp
merge(x_root, y_root);
```
改为
```cpp
if(x_root！=y_root)merge(x_root, y_root);
```
by wkywkywky @ 2019-08-22 21:07:52