欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1118 Birds in Forest (25分) / 并查集

程序员文章站 2022-06-11 14:28:22
...

题目描述

1118 Birds in Forest (25分) / 并查集
1118 Birds in Forest (25分) / 并查集

AC代码

#include<bits/stdc++.h>
using namespace std;
int father[10005];
int find(int x){
	while(father[x]>=0){
		x=father[x];
	}
	return x;
}
void Union(int a,int b){
	int fa=find(a),fb=find(b);
	if(fa!=fb){					//按秩归并 
		if(father[fa]<father[fb]){
			father[fa]+=father[fb];
			father[fb]=fa;
		}
		else{
			father[fb]+=father[fa];
			father[fa]=fb;
		}
	}
}
int main() {
	memset(father,-1,sizeof(father)); //注意初始化 
	int n,maxnum=0;cin>>n;
	while(n--){
		int k,root,temp;cin>>k;
		for(int i=0;i<k;i++){
			scanf("%d",&temp);
			maxnum=max(maxnum,temp);  //更新birds id的最大值 
			if(i==0) root=temp;  //将每张图片的第一只bird作为根结点 
			else Union(temp,root);
		}
	}
	int cnt=0,num=0;
	for(int i=1;i<=maxnum;i++){
		if(father[i]<0) {
			cnt++;       //集合个数 
			num-=father[i];    //number of birds
		}
	}
	printf("%d %d\n",cnt,num);
	int k;cin>>k;
	while(k--){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%s\n",find(a)==find(b)?"Yes":"No");
	}
	return 0;
}