这道题是下午看的,当时看了不会,后来看算法导论上有,有看了一些其他的资料,就做出来了。不过杭电数据坑爹啊,,,竟然有n=0的情况,让我wr了好几次。。。。题目:
More is better
Time Limit: 5000/1000 MS (Java/Others)Memory Limit: 327680/102400 K (Java/Others)
Total Submission(s): 4078Accepted Submission(s): 1511
Problem Description
Mr Wang wants some boys to help him with a project. Because the project is rather complex,the more boys come, the better it will be. Of course there are certain requirements.
Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are
still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.
Input
The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000)
Output
The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.
Sample Input
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
Sample Output
4
2
Hint
A and B are friends(direct or indirect), B and C are friends(direct or indirect),
then A and C are also friends(indirect).
In the first sample {1,2,5,6} is the result.
In the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers.
ac代码:
分享到:
相关推荐
2018-2019-1的杭电大物2试卷,附答案 2018-2019-1的杭电大物2试卷,附答案 2018-2019-1的杭电大物2试卷,附答案
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的竞赛项目学习资料,作为参考学习借鉴。...java算法刷题,备赛杭电,PAT,蓝桥杯等源码+项目说明.zip
acm杭电课件+博弈的一篇英文论文+背包九讲的论文
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
杭电ACM参考代码 里面有200+到算法的标程!杭电ACM参考代码 里面有200+到算法的标程!
杭电acm PPT合集,很多内容,很多分类。
经过辛苦的整理,本文件内含杭电,浙大,北大acm练习题上千道,里面含有答案,并且采用chm格式方便使用,对acm感兴趣的赶紧来下载吧!
杭电ACM博弈题合集分享.pdf
杭电数据库期末复习资料集,助你轻松备考~
杭电ACM分类杭电ACM分类杭电ACM分类杭电ACM分类
杭电计算机系统结构期末复习资料集,助你轻松考试~
杭电离散答案 杭电离散答案 杭电离散答案 杭电离散答案
杭电 并查集 详细介绍了有关并查集的算法,在简单的ppt中浓缩了并查集的精华
杭电ACM 课件 基本上一些基础算法都有了,像DP 计算几何 贪心 搜索 并查集...
杭州电子科技大学 数据结构试卷及答案 杭电 合集
杭电acm课件,数论,动态规划,博弈,并查集,探索,贪心,涵盖了入门必需的基本元素,强力推荐
杭电 金工实习报告 杭电 金工实习报告 杭电 金工实习报告
考研杭电数据结构试卷
杭电日历----xxyw
杭电计算机操作系统期末复习资料集,有2011的期末试卷小结哦,助你轻松考试~