亲戚并查集这样处理为什么不可以
  • 板块P1551 亲戚
  • 楼主benjie857
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/8/23 13:01
  • 上次更新2023/11/6 19:36:35
查看原帖
亲戚并查集这样处理为什么不可以
327960
benjie857楼主2020/8/23 13:01
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,p,parent[100005],rank[100005];
int find_root(int x){//找出祖先 
	int x_root=x;//自己的爸爸是自己,自己就是祖先 
	while(parent[x_root]!=-1){
		x_root=parent[x_root];
	}
	return x_root;
	//return x_root = parent[x]==-1?x:find_root(parent[x]);
}
void nion_set(int x,int y){
	int x_root=find_root(x);
	int y_root=find_root(y);
	if(x_root==y_root)return;
	if(rank[x_root]>rank[y_root]){
		parent[y_root]=x_root;
	}else if(rank[x_root]<rank[y_root]){
		parent[x_root]=rank[y_root];
	}else{
		parent[x_root]=y_root;
		rank[y_root]++;
	}
}
int main(){
	cin>>n>>m>>p;
	memset(parent,-1,sizeof(parent));
	memset(rank,0,sizeof(rank));
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		nion_set(x,y);
	}
	for(int i=0;i<p;i++){
		int tp,tq;
		cin>>tp>>tq;
		if(find_root(tp)==find_root(tq)){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
}
2020/8/23 13:01
加载中...