70分和100分的区别我看不出来,求帮助分析

P3367 【模板】并查集

KouMoSir @ 2023-06-19 13:40:18

这道题我交了两个版本

一个70分,一个100分

70分代码:

#include<iostream>
using namespace std;
#include<iostream>
using namespace std;
const int N=1e4,M=2e5;
int r[N];
int z,x,y,n,m;
int find(int k){
    if(r[k]==k)return k;
    return r[k]=find(r[k]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)r[i]=i;
    for(int i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1)
            r[find(x)]=find(y);
        else
            if(find(x)==find(y))cout<<"Y"<<endl;
            else cout<<"N"<<endl;
    }
    return 0;
}

100分代码:

#include<iostream>
using namespace std;
#include<iostream>
using namespace std;
const int N=1e4,M=2e5;
int z,x,y,n,m;
int r[N];
int find(int k){
    if(r[k]==k)return k;
    return r[k]=find(r[k]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)r[i]=i;
    for(int i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1)
            r[find(x)]=find(y);
        else
            if(find(x)==find(y))cout<<"Y"<<endl;
            else cout<<"N"<<endl;
    }
    return 0;
}

两份代码唯一的区别在int的定义那两行的顺序不同,为什么会产生30分差距呢?

我复制70分代码,将int r[N] 与int z,x,y,n,m交换行,即可100分通过。

可能是我基础太薄弱,真的不知道改如何分析这种情况。


by World_Creater @ 2023-06-19 13:42:20

数组越界了。

N 改大一点就没问题了


by caohan @ 2023-06-19 13:42:32

内存访问顺序


by QAQ__ @ 2023-06-19 14:13:25

@KouMoSir 我猜是因为第一个代码 r 数组越界之后改掉了下一个内存 z 的内容。第二个代码 r 越界之后改的是空白内存,所以 AC 了。


by KouMoSir @ 2023-06-19 14:56:21

@QAQ__ 感谢解答,老半天原来是数组越界了,这下明白了


|