求助dalao为什么是RE

P3367 【模板】并查集

86158615777a @ 2018-08-08 20:38:19

#include<bits/stdc++.h>
using namespace std;
int father[10001];
char result[200001];
int find(int); 
void unionn(int ,int);
int main()
{
    int n,m,i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    father[i]=i;
    for(i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&w,&x,&y);
        if(w==1){
            int r1=find(x),r2=find(y);
            if(r1!=r2)
            unionn(r1,r2);
        }
        if(w==2)
        {
            int r1=find(x);
            int r2=find(y);
            if(r1!=r2) result[i]='N';
            else result[i]='Y';
        }
    }
    for(i=1;i<=m;i++)
    if(result[i]=='Y'||result[i]=='N') cout<<result[i]<<endl;
}
int find(int x)
{
    while(x!=father[x]) x=father[x];
    return x;
}
void unionn(int x,int y)
{
     father[y]=x;
}

by Viston @ 2018-08-08 20:40:03

看不出有什么毛病啊


by 马峰 @ 2018-08-08 20:43:54

您这应该是t了吧,没路径压缩


by 顾z @ 2018-08-08 20:48:44

那啥 ,为啥转成离线做呢


by 顾z @ 2018-08-08 20:51:58

提点意见

1路径压缩 2在线 (逃


by 顾z @ 2018-08-08 20:54:23

@ 86158615777a


by 86158615777a @ 2018-08-08 21:12:51

各位大佬,我知道原因了:1.数组开小了,少开了一个。2.我路径压缩用了非递归方法,而非递归方法超时了,而递归方法没超时。请教各位大佬,这是为什么?


by Papaya @ 2018-08-08 21:20:56

@86158615777a 数组小了吗?不见得 我把你的代码压缩之后就A了 (您可以把您的递归代码和非递归代码发出来看看)


|