因为申必原因WA了

P3367 【模板】并查集

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'

请解不等式组

x<0 x>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_ 后面那个问题是因为 \texttt{find(x)} 是找 x 的祖先,祖先不一定只有一级。


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]访问的就不是最新的祖先


| 下一页