关于并查集的细节
查看原帖
关于并查集的细节
246979
SalomeJLQ楼主2020/9/5 10:07

首先很早之前我交上去的是这份

#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。

这是否代表这些语句是等价的?

2020/9/5 10:07
加载中...