并查集练习

前言：

关于并查集的一些训练题。

正文：

1.亲戚：

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int fa[N];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
bool qq(int x,int y){
	return find(x)==find(y);
}
int main(){
	int n,m,p,a,b;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)fa[i]=i;
//	for(int i=1;i<=n;i++)cout<<fa[i]<<" ";
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		merge(a,b);
	}
//	for(int i=1;i<=n;i++)cout<<find(i)<<" ";
	for(int i=1;i<=p;i++){
		cin>>a>>b;
	//	cout<<find(a)<<" "<<find(b)<<endl;
		if(qq(a,b))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

2.奶酪:

#include<bits/stdc++.h>
using namespace std;
typedef struct su{
	int x;
	int y;
	int z;
}hole;
double dist(hole a,hole b){
	return sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2)+pow((a.z-b.z),2));
}
hole ho[1005];
int fa[1005];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(ho,0,sizeof(ho));
		int n,h,r,x,y,z;
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
		for(int i=1;i<=n;i++){
			cin>>x>>y>>z;
			ho[i].x=x,ho[i].y=y,ho[i].z=z;
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(dist(ho[i],ho[j])<=2*r)merge(i,j);
			}
		}
		int flag=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(ho[j].z<=r&&ho[i].z>=h-r&&find(i)==find(j)){
					flag=1;
					break;
				}
			}
			if(flag)break;
		}
		if(flag)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

3.村村通:

#include<bits/stdc++.h>
using namespace std;
int fa[1005];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
int main(){
	int n,m;
	while(cin>>n&&n!=0){
		cin>>m;
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			merge(x,y);
		}
		int ans=0;
		for(int i=1;i<n;i++){
			if(find(i)!=find(i+1)){
				ans++;
				merge(i,i+1);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

4.修复公路:

#include<bits/stdc++.h>
using namespace std;
int fa[1000005];
int n,m,x,y,t;
typedef struct su{
	int x;
	int y;
	int t;
}vill;
bool cmp(vill x,vill y){
	return x.t<y.t;
}
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
bool check()
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i) sum++;//统计独立集合的个数
		if(sum==2) return 0;//发现有两个就返回false应该会省一点时间
	}
	return 1;//只有1个集合，返回true
}//判断集合个数
vill v[1000005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>t;
		v[i].x=x;
		v[i].y=y;
		v[i].t=t;
	}
	sort(v+1,v+m+1,cmp);
	for(int i=1;i<m;i++){
		int cnt=1;
		merge(v[i].x,v[i].y);
		if(check()){
			cout<<v[i].t<<endl;
			return 0;
		}
	}
	cout<<"-1"<<endl;
	return 0;
}