SalomeJLQ @ 2020-09-05 10:07:52
首先很早之前我交上去的是这份
#include<bits/stdc++.h>
using namespace std;
int n,m,z,x,y,f[10005];
int findd(int xx){
if(f[xx]==xx)return xx;
return f[xx]=findd(f[xx]);
}
void check(int xx,int yy){
if(findd(xx)==findd(yy))cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
while(m--){
cin>>z>>x>>y;
if(z==1)f[findd(x)]=findd(y);
else check(x,y);
}
return 0;
}
这个是AC的。
然后我今天把里面的
if(z==1)f[findd(x)]=findd(y);
修改为 if(z==1)f[findd(x)]=findd(f[y]);
结果也是AC了。
接着我再修改,把这句话变成了 if(z==1)f[findd(f[x])]=findd(f[y]);
结果仍然AC。
然后我又把里面的
if(findd(xx)==findd(yy))cout<<"Y"<<endl;
依次修改为了 if(findd(f[xx])==findd(f[yy]))cout<<"Y"<<endl;
和 if(f[findd(xx)]==findd(f[yy]))cout<<"Y"<<endl;
,还是AC。
这是否代表这些语句是等价的?
by MatrixCascade @ 2020-09-05 10:13:51
这不是废话吗,肯定可以A啊
by Semsue @ 2020-09-05 10:14:07
如果意义不对的的话不好记容易记错
by MatrixCascade @ 2020-09-05 10:14:13
@爵士 所以你是没完全理解并查集?
by Semsue @ 2020-09-05 10:14:39
@爵士 我的意思是你后面的代码的“意义”
by 超级玛丽王子 @ 2020-09-05 10:15:39
@爵士 并查集做路径压缩,所以x=f[x]
是一定的
by SalomeJLQ @ 2020-09-05 10:16:45
@Illusory_ 差不多,