1118 Birds in Forest(35行代码+详细注释)

这篇具有很好参考价值的文章主要介绍了1118 Birds in Forest(35行代码+详细注释)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

分数 25

全屏浏览题目

切换布局

作者 CHEN, Yue

单位 浙江大学

Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are on the same tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (≤104) which is the number of pictures. Then N lines follow, each describes a picture in the format:

K B1​ B2​ ... BK​

where K is the number of birds in this picture, and Bi​'s are the indices of birds. It is guaranteed that the birds in all the pictures are numbered continuously from 1 to some number that is no more than 104.

After the pictures there is a positive number Q (≤104) which is the number of queries. Then Q lines follow, each contains the indices of two birds.

Output Specification:

For each test case, first output in a line the maximum possible number of trees and the number of birds. Then for each query, print in a line Yes if the two birds belong to the same tree, or No if not.

Sample Input:

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

Sample Output:

2 10
Yes
No

代码长度限制

16 KB

时间限制

150 ms

内存限制

64 MB

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,k,bird,exist[N],q,a,b,cnt[N],Max,p[N];
unordered_map<int,int>mp;
int find(int x){//并查集找根结点的经典操作 
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    cin>>n;
    for(int i=1;i<=N;i++)p[i]=i;//初始化并查集 
    for(int i=0;i<n;i++){
        cin>>k;
        vector<int>v;
        for(int j=0;j<k;j++){
            cin>>bird;
            v.push_back(bird);//输入鸟 
            exist[bird]=1;//出现过的鸟置为1 
        }
        for(int j=1;j<k;j++)//将该照片里的鸟都合并到第一个鸟上 
             p[find(v[j])]=find(v[0]);    
    }
    int pos=1;
    while(exist[pos])pos++;//获得总共鸟的数量 
    for(int i=1;i<pos;i++)mp[find(i)]=1;//获得集合数量 
    cout<<mp.size()<<' '<<pos-1<<endl;//输出集合数量和鸟数 
    cin>>q;
    for(int j=0;j<q;j++){
        cin>>a>>b;
        if(find(a)==find(b))puts("Yes");//若在一个集合 
        else puts("No"); //若不在一个集合 
    }
    return 0;
}
文章来源地址https://www.toymoban.com/news/detail-475803.html

到了这里,关于1118 Birds in Forest(35行代码+详细注释)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MVSNet代码超详细注释(PyTorch)

    网上解读MVSNet的博客已经很多了,大家可以自选学习,但更重要的是阅读理解原文,以及自己动手跑跑代码! MVSNet服务器环境配置及测试 https://blog.csdn.net/qq_43307074/article/details/128011842 【论文简述及翻译】MVSNet:Depth Inference for Unstructured Multi-view Stereo(ECCV 2018) https://blog.csd

    2024年02月02日
    浏览(50)
  • DenseNet代码复现+超详细注释(PyTorch)

    关于DenseNet的原理和具体细节,可参见上篇解读:经典神经网络论文超详细解读(六)——DenseNet学习笔记(翻译+精读+代码复现) 接下来我们就来复现一下代码。 整个DenseNet模型主要包含三个核心细节结构,分别是 DenseLayer (整个模型最基础的原子单元,完成一次最基础的

    2023年04月23日
    浏览(53)
  • ResNeXt代码复现+超详细注释(PyTorch)

    ResNeXt就是一种典型的混合模型,由基础的Inception+ResNet组合而成,本质在gruops分组卷积,核心创新点就是用一种平行堆叠相同拓扑结构的blocks代替原来 ResNet 的三层卷积的block,在不明显增加参数量级的情况下提升了模型的准确率,同时由于拓扑结构相同,超参数也减少了,便

    2024年02月15日
    浏览(51)
  • ResNet代码复现+超详细注释(PyTorch)

    关于ResNet的原理和具体细节,可参见上篇解读:经典神经网络论文超详细解读(五)——ResNet(残差网络)学习笔记(翻译+精读+代码复现) 接下来我们就来复现一下代码。 源代码比较复杂,感兴趣的同学可以上官网学习:  https://github.com/pytorch/vision/tree/master/torchvision 本

    2024年02月11日
    浏览(43)
  • 【算法】顺时针打印矩阵(图文详解,代码详细注释

    目录 题目 代码如下: 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则打印出数字:1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 这一道题乍一看,没有包含任何复杂的数据结构和高级算法,似乎蛮简单的。但

    2024年04月26日
    浏览(37)
  • 1146 Topological Order(31行代码+详细注释)

    分数 25 全屏浏览题目 作者 CHEN, Yue 单位 浙江大学 This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options. Input Specification: Each input file contains one test case. For each

    2024年02月06日
    浏览(78)
  • 非极大值抑制详细原理(NMS含代码及详细注释)

    作者主页: 爱笑的男孩。的博客_CSDN博客-深度学习,YOLO,活动领域博主 爱笑的男孩。擅长深度学习,YOLO,活动,等方面的知识,爱笑的男孩。关注算法,python,计算机视觉,图像处理,深度学习,pytorch,神经网络,opencv领域. https://blog.csdn.net/Code_and516?type=collect 个人介绍:打工人。 分享内容

    2023年04月21日
    浏览(55)
  • 五子棋小游戏 java版(代码+详细注释)

    游戏展示         这周闲来无事,再来写个五子棋小游戏。基本功能都实现了,包括人人对战、人机对战。界面布局和功能都写的还行,没做到很优秀,但也不算差。如有需要,做个java初学者的课程设计或者自己写着玩玩也都是不错的(非常简单,小白照着就能写出来)。

    2024年02月07日
    浏览(47)
  • 【华为OD机试真题 C++】1118 - 最大利润 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Python语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 商人经营一家店铺, 有number种商品,由于仓库限

    2024年02月04日
    浏览(65)
  • 通俗易懂的知识蒸馏 Knowledge Distillation(下)——代码实践(附详细注释)

    第一步:导入所需要的包 第二步:定义教师模型 教师模型网络结构(此处仅举一个例子):卷积层-卷积层-dropout-dropout-全连接层-全连接层 第三步:定义训练教师模型方法 正常的定义一个神经网络模型 第四步:定义教师模型测试方法 正常的定义一个神经网络模型 第五步:

    2024年02月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包