因为申必原因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 Kio_ @ 2020-08-15 11:03:44

@星光0000 噢噢懂了qwq

那要怎么做到合并后a[x]依然访问最新的祖先呢......全部for一遍吗


by StarLbright40 @ 2020-08-15 11:05:06

@Kio_ 你不是在每次查询时都find了一遍嘛(


by sfmmdm @ 2020-08-15 11:45:27

@Kio_ 只有在查询的时候才会进行路径压缩,其他时候它是不会动的。


by sfmmdm @ 2020-08-15 11:46:00

@Kio_ 是的,这样得不偿失


by Kio_ @ 2020-08-15 11:51:27

@sfmmdm 好的,谢谢大佬_(:з」∠)


by sfmmdm @ 2020-08-15 12:25:06

@Kio_ 不用谢


上一页 |