关于并查集的细节

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 Schwarzkopf_Henkal @ 2020-09-05 10:09:14

是啊


by SalomeJLQ @ 2020-09-05 10:09:31

哦。


by Sya_Resory @ 2020-09-05 10:09:40

本来就是啊 x和f[x]是在同一个集合里的


by SalomeJLQ @ 2020-09-05 10:09:50

那么用哪个更好


by SalomeJLQ @ 2020-09-05 10:10:18

@Sky_Dreamer 哦谢谢


by Semsue @ 2020-09-05 10:10:35

要不然呢?


by Sya_Resory @ 2020-09-05 10:10:58

@爵士 常数的差距 比哪个好意义不大吧(


by SalomeJLQ @ 2020-09-05 10:12:28

哦谢谢


by Semsue @ 2020-09-05 10:12:48

@爵士 肯定用原来的啊,你后来改的的“意义”是什么?


by SalomeJLQ @ 2020-09-05 10:13:18

@Flying_Bird 尝试一下能不能AC


| 下一页