PAT 甲级 1118(Birds in Forest)
程序员文章站
2022-06-11 14:27:52
...
题目要求
翻译
一幅画里面的鸟为同一棵树上的,问有多少棵树和多少只鸟,以及对于两只鸟判断是否在同一个树上。
代码
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
set<int> ids;
int Rank[10010],parent[10010];
void init()
{
for(int i=0;i<10010;i++)
{
parent[i]=i;
}
memset(Rank,0,sizeof(int));
}
int find(int p)
{
while (p!=parent[p])
{
parent[p]= parent[parent[p]];
p=parent[p];
}
return p;
}
void Union(int p,int q)
{
int proot=find(p),qroot=find(q);
if(proot==qroot) return;
if(Rank[proot]>Rank[qroot]){
parent[qroot]=proot;
}else if(Rank[proot]<Rank[qroot]){
parent[proot]=qroot;
}else
{
parent[qroot]=proot;
Rank[qroot]++;
}
}
int main()
{
init();
int n;
cin>>n;
for(int i=0,k;i<n;i++)
{
scanf("%d",&k);
int b,tmp;
for(int j=0;j<k;j++)
{
scanf("%d",&b);
ids.insert(b);
if(j!=0) Union(tmp,b);
tmp=b;
}
}
vector<int> tmp[10010];
set<int> s;
for(int id:ids){
int temp=find(id);
s.insert(temp);
tmp[temp].emplace_back(id);
}
printf("%d %d\n",s.size(),ids.size());
scanf("%d",&n);
while (n--)
{
int i,j;
scanf("%d %d",&i,&j);
if(find(i)==find(j)) printf("Yes\n");
else
{
printf("No\n");
}
}
system("pause");
}
思路
同样需要用到并查集。
可以将找到的父节点放到集合,或者vector中,放进去的数量就是多少棵树;
将所有节点放到集合中,有多少数量就是多少鸟;
判断是否在同一棵树就很简单了,只要find
就可以了。
推荐阅读
-
1118 Birds in Forest (25分) (并查集)
-
PAT 甲级 1118Birds in Forest (25分)
-
A1118 Birds in Forest [并查集]
-
1118 Birds in Forest (25分) / 并查集
-
PAT 甲级 1118(Birds in Forest)
-
PAT甲级 1118 Birds in Forest 并查集
-
1118 Birds in Forest (25分)【关于PAT中使用并查集的坑点】
-
1118 Birds in Forest (25分)
-
PAT_甲级_1118 Birds in Forest (25point(s)) (C++)【并查集】