Vijos P1034家族

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入格式

输出格式

各点1S

cdwind整理提交

题解:基础并查集

AC代码:

#include<iostream>
using namespace std;
int m,n,p,uset[5001],rank[5001],tempx,tempy;
int find(int x){
	while(x!=uset[x]) x=find(uset[x]);
	return x;
}
void union_set(int x,int y){
	if((x=find(x))==(y=find(y))) return ;
	if(rank[x]>rank[y]) uset[y]=x;
	else {
		uset[x]=y; 
		if(rank[x]==rank[y])rank[y]++;
	}
}
int main(){
		cin>>n>>m>>p; 
		for(int i=1;i<=n;i++){
			uset[i]=i; rank[i]=1;
		}
		for(int i=0;i<m;i++){
			cin>>tempx>>tempy;
			union_set(tempx,tempy);
		}
		for(int i=0;i<p;i++){
			cin>>tempx>>tempy;
			if(find(tempx)==find(tempy))
			cout<<"Yes\n";
			else cout<<"No\n";
		}
	return 0;
}