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__ 感谢解答,老半天原来是数组越界了,这下明白了