为什么不初始化g[i]=i就会MLE？

P3367 【模板】并查集

zvagowy @ 2023-08-17 08:26:33

以下为MLE代码

#include<iostream>  
using namespace std;  
int g[10001];  
int find(int x){  
    if(g[x]==0) return x;//这里不一样  
    return g[x]=find(g[x]);
}
int main(){
    int n,m,i,z,x,y;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1) g[find(x)]=find(y);
        else if(find(x)==find(y)) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}

以下为AC代码

#include<iostream>
using namespace std;
int g[10001];
int find(int x){
    if(g[x]==x) return x;//这里不一样
    return g[x]=find(g[x]);
}
int main(){
    int n,m,i,z,x,y;
    cin>>n>>m;
    for(i=1;i<=n;i++) g[i]=i;//初始化
    for(i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1) g[find(x)]=find(y);
        else if(find(x)==find(y)) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}

这两个递归的空间复杂度能不一样？

by zqy729 @ 2023-08-17 08:29:18

@zvagowy 会无限循环，然后爆栈

by zqy729 @ 2023-08-17 08:31:09

你那个代码，根节点的父亲节点是它自身，所以递归函数永远到不了边界，会无限循环

by zvagowy @ 2023-08-17 08:42:04

@zqy729 没初始化的那个递归基础不一样，if(g[x]==0) return x;所以可以结束递归啊，本地样例数据输出是没问题的

by zqy729 @ 2023-08-17 08:56:41

@zvagowy 是我的失误。不过你那个代码，g[x]可以直接查询。但是你的代码一无法直接查询，每次查询都会重新从头开始查询，这样会导致复杂度大大提高。

by zqy729 @ 2023-08-17 09:01:36

贴一组数据 data1.in

10 20
1 4 8
1 1 2
1 7 2
2 6 8
1 3 2
2 9 5
1 7 1
2 9 10
1 1 5
2 1 9
1 4 8
2 7 9
2 9 1
2 9 6
2 10 8
1 3 5
1 6 10
1 4 8
2 5 4
1 8 4

data.out

N
N
N
N
N
N
N
N
N

by zvagowy @ 2023-08-17 09:46:04

哦哦，谢谢大佬！发现问题了，就是如果合并同一个根节点，会变成g[x]=x，然后就不符合我的递归结束条件了……

|