关于并查集的细节

P3367 【模板】并查集

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_ 差不多,


上一页 |