brnhbrnh @ 2019-08-05 21:23:07
#include <bits/stdc++.h>
using namespace std;
const int maxn=10010;
int N=0,M=0;
int f[maxn];
int find(int k)
{
if(f[k]==k)return k;
return f[k]=find(f[k]);
}
bool compar(int a,int b)
{
return find(a)==find(b);
}
void combine(int a,int b)
{
f[find(b)]=f[a];
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) f[i]=i;
int x=0,y=0,z=0;
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&z,&x,&y);
if(z==1) combine(x,y);
else
{
if(compar(x,y)) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
我拿这个模板都已经过了kruskal了为啥并查集模板过不去了233333实在找不到原因了
by dlydly @ 2019-08-05 21:29:11
???
by 反手一只MJJ @ 2019-08-05 21:29:51
@brnhbrnh
void combine(int a,int b)
{
f[find(b)]=f[a];
}
是不是应给改为:
void combine(int a,int b)
{
f[find(b)]=find(a);
}
by WAutomaton @ 2019-08-05 21:30:56
@brnhbrnh 合并前要先判断两个点是否在同一集合中
by 反手一只MJJ @ 2019-08-05 21:31:58
楼上说的+1
awa
by 蒟蒻365 @ 2019-08-05 21:35:10
如果在一个集合中合并了不跟没合并一样吗qaq
by brnhbrnh @ 2019-08-05 21:50:21
谢谢各位巨佬233我想着如果父亲一样就只会走一遍而已,没什么关系23333
by brnhbrnh @ 2019-08-06 20:20:01
@反手一只MJJ 是吧,我之前直接改成a的,其实不压缩路径是差不多的