1118 Birds in Forest (25分) / 并查集
程序员文章站
2022-06-11 14:28:22
...
题目描述
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;
}
推荐阅读
-
AtCoderPetrozavodskContest001D-Forest连通块+并查集+贪心
-
1118 Birds in Forest (25分) (并查集)
-
A1118 Birds in Forest [并查集]
-
1118 Birds in Forest (25分) / 并查集
-
PAT甲级 1118 Birds in Forest 并查集
-
1118 Birds in Forest (25分)【关于PAT中使用并查集的坑点】
-
AtCoderPetrozavodskContest001D-Forest连通块+并查集+贪心
-
PAT_甲级_1118 Birds in Forest (25point(s)) (C++)【并查集】