+-
PAT_甲级_1118 Birds in Forest
首页 专栏 c++ 文章详情
0

PAT_甲级_1118 Birds in Forest

乔梓鑫 发布于 2 月 26 日

题目大意

现在有N张图片,每一张图片里面有K只鸟,在同一张图片中的鸟属于同一棵树,计算森林中树木的最大数目,并且对于任意一对鸟,判断是否在同一棵树上。

算法思路

本题考查并查集的应用,我们使用set集合birds保存所有的输入的鸟,并在输入每一张图片的时候,将其中所有的鸟进行合并为一组,然后对于birds中所有的鸟类根据其祖先归并为一棵树,并存放到set集合trees中,最后对于任意两个鸟的编号,只需要比较father数组的值是否相同即可。

注意点

1、查找father的方法得使用路径压缩,不然会有一个测试点超时。

提交结果

AC代码

#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>

using namespace std;

unordered_set<int> birds;
unordered_set<int> trees;

int father[10005];

int findFather(int x){
    int a = x;
    while(x!=father[x]){
        x = father[x];
    }
    while (a!=father[a]){
        int z = father[a];
        father[a] = x;
        a = z;
    }
    return x;
}

void Union(int a,int b){
    int fa = findFather(a);
    int fb = findFather(b);
    if(fa!=fb){
        father[fa] = fb;
    }
}

int main() {
    for(int i=0;i<=10000;++i){
        father[i] = i;
    }
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        int k;
        scanf("%d",&k);
        vector<int> t(k);
        for(int j=0;j<k;++j){
            scanf("%d",&t[j]);
            birds.insert(t[j]);
            if(j!=0){
                Union(t[j],t[j-1]);
            }
        }
    }
    for(auto it:birds){
        int f=findFather(it);
        trees.insert(f);
    }
    printf("%lu %lu\n",trees.size(),birds.size());
    int query;
    scanf("%d",&query);
    for(int i=0;i<query;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        if(father[a]==father[b]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}
c++ 数据结构和算法
阅读 30 发布于 2 月 26 日
收藏
分享
本作品系原创, 采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
PAT题解
关注专栏
avatar
乔梓鑫

主要分享个人学习经验和心得

468 声望
5 粉丝
关注作者
0 条评论
得票 时间
提交评论
avatar
乔梓鑫

主要分享个人学习经验和心得

468 声望
5 粉丝
关注作者
宣传栏
目录

题目大意

现在有N张图片,每一张图片里面有K只鸟,在同一张图片中的鸟属于同一棵树,计算森林中树木的最大数目,并且对于任意一对鸟,判断是否在同一棵树上。

算法思路

本题考查并查集的应用,我们使用set集合birds保存所有的输入的鸟,并在输入每一张图片的时候,将其中所有的鸟进行合并为一组,然后对于birds中所有的鸟类根据其祖先归并为一棵树,并存放到set集合trees中,最后对于任意两个鸟的编号,只需要比较father数组的值是否相同即可。

注意点

1、查找father的方法得使用路径压缩,不然会有一个测试点超时。

提交结果

AC代码

#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>

using namespace std;

unordered_set<int> birds;
unordered_set<int> trees;

int father[10005];

int findFather(int x){
    int a = x;
    while(x!=father[x]){
        x = father[x];
    }
    while (a!=father[a]){
        int z = father[a];
        father[a] = x;
        a = z;
    }
    return x;
}

void Union(int a,int b){
    int fa = findFather(a);
    int fb = findFather(b);
    if(fa!=fb){
        father[fa] = fb;
    }
}

int main() {
    for(int i=0;i<=10000;++i){
        father[i] = i;
    }
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        int k;
        scanf("%d",&k);
        vector<int> t(k);
        for(int j=0;j<k;++j){
            scanf("%d",&t[j]);
            birds.insert(t[j]);
            if(j!=0){
                Union(t[j],t[j-1]);
            }
        }
    }
    for(auto it:birds){
        int f=findFather(it);
        trees.insert(f);
    }
    printf("%lu %lu\n",trees.size(),birds.size());
    int query;
    scanf("%d",&query);
    for(int i=0;i<query;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        if(father[a]==father[b]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}