Kio_ @ 2020-08-15 10:39:11
不知道为啥,用快读写就炸了,换成scanf就过了
原WA代码:
#include<cstdio>
using namespace std;
int a[10020];
int find(int x)
{
if(x!=a[x])a[x]=find(a[x]);
return a[x];
}
void _union(int x,int y)
{
int x1=find(x),y1=find(y);
a[y1]=a[x1];
}
int read()
{
int num=0;
char c=getchar();
while(c<'0'&&c>'9')c=getchar();
while('0'<=c&&c<='9'){
num=num*10+c-'0';c=getchar();}
return num;
}
int n,m;
int x,y,z;
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++)
{
z=read();
x=read();
y=read();
//printf("Z:%d ",z);
if(z==1)_union(x,y);
if(z==2)
{
//if(a[x]==a[y])printf("Y\n");
if(find(x)==find(y))printf("Y\n");
else printf("N\n");
}
}
return 0;
}
把快读换成 scanf("%d %d %d",&z,&x,&y);就AC了
emmm还有个问题,为啥必须得写 if(find(x)==find(y)),不能写if(a[x]==a[y]),(写后者没过样例)
求大佬指导QwQ
by sslhky @ 2020-08-15 10:41:10
是while(c<'0'||c>'9')...
by JRzyh @ 2020-08-15 10:41:59
c<'0'&&c>'9'
请解不等式组
by Ink_Bottle @ 2020-08-15 10:42:08
所以您快读是对的吗
by Sampson_YW @ 2020-08-15 10:42:11
快读中的while(c<'0'&&c>'9')c=getchar();
改为while(c<'0'||c>'9')c=getchar();
by Sktic @ 2020-08-15 10:43:41
“emmm还有个问题,为啥必须得写 if(find(x)==find(y)),不能写if(a[x]==a[y]),(写后者没过样例)” 祖先···········判断是同一个集合内的啊
by 仗剑_天涯 @ 2020-08-15 10:44:44
@Zhaoyuhang2008
x=2147483647+1
by Eason_AC @ 2020-08-15 10:45:46
@Kio_ 快读中
while(c<'0'&&c>'9')
改成
while(c<'0'||c>'9')
应该就OK了
by Eason_AC @ 2020-08-15 10:47:02
@Kio_ 后面那个问题是因为
by Kio_ @ 2020-08-15 10:52:00
@Eason_AC 快读问题解决了,谢谢大佬qwq
可是后面find的问题,我find函数里面不是做过路径压缩了吗,那a[x]不是能直接访问祖先了吗......?
by StarLbright40 @ 2020-08-15 10:53:59
@Kio_ 不能,如果你之前合并过,那a[x]访问的就不是最新的祖先