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

PAT 甲级 1118(Birds in Forest)

程序员文章站 2022-06-11 14:27:52
...

PAT 甲级 1042

题目要求

PAT 甲级 1118(Birds in Forest)

翻译

一幅画里面的鸟为同一棵树上的,问有多少棵树和多少只鸟,以及对于两只鸟判断是否在同一个树上。

代码

#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就可以了。