More is better
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 327680/102400 K (Java/Others)
Total Submission(s): 10355 Accepted Submission(s): 3814
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.
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.题意:
给出n种朋友关系,在这么多堆朋友圈中,输出最多人数一组的人数。
思路:
并查集。增加一个数组rank来统计某个节点下面有多少人,合并的时候累加一层即可。
AC:
#include<stdio.h> #define max 10000000 int root[max],rank[max]; int find(int a) { int x=a,t; while(root[x]!=x) x=root[x]; while(x!=a) { t=root[a]; root[a]=x; a=t; } return x; } int main() { int n; while(scanf("%d",&n)!=EOF) { int a,b,m=0,sum=1; for(int i=1;i<max;i++) { root[i]=i; rank[i]=1; } while(n--) { int fa,fb; scanf("%d%d",&a,&b); fa=find(a); fb=find(b); if(a>sum) sum=a; if(b>sum) sum=b; if(fa==fb) continue; else { rank[fb]+=rank[fa]; //只需要增加这一句,来求叠加人数 root[fa]=fb; } } for(int i=1;i<=sum;i++) if(rank[i]>m) m=rank[i]; //查找rank中最大值即为所求 printf("%d\n",m); } return 0; }
总结:
看清题目,不要钻牛角尖。
相关推荐
精品文档 欢迎下载
Risk parity is a type of asset allocation strategy that has become increasingly popular in the aftermath of the global financial crisis
Apixaban or enoxaparin_ Which is better forthromboprophylaxis after total hip a
Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. ...
Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. ...
P. M. Chen 和B. D. Noble 首次提出虚拟化方面的语义鸿沟问题。作者认为虚拟机比较物理机更好,因为我们可以很方便的在位于客户操作系统下面的虚拟机监视器(VMM)里面增加一些服务,如安全日志、入侵检测与防御系统...
The Gourmet iOS Developer's Cookbook Even More Recipes for Better iOS App Development 英文无水印原版pdf pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试都可以打开 本资源转载...
The Gourmet iOS Developer's Cookbook Even More Recipes for Better iOS App Development 英文azw3 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
主要是对linux和bsd进行比较,不过并不是很全面的,但是也可以看到接近于unix的bsd的优点
Better 20188888888~集干货、音乐、视频、打卡于一体的app
4、有一个字符串“Doing is better than saying”,编写程序对该字符串按照空格进行拆分,再对拆分后的结果进行合并连接成字符串。 5、“dsfs.c.asdf.123@126.comasfdsd.asf@qq.comasdf.sd.sadffds@163.com”提取这...
better-scroll.js
What better way is there to learn a programming language than with a game-oriented approach? If you ask the many readers that have made this book's prequel, PYTHON PROGRAMMING FOR THE ABSOLUTE ...
Better Deep Learning Train Faster, Reduce Overfitting, and Make Better Predictions by Jason Brownlee 26 step-by-step lessons, 575 pages. quotes from papers and books. step-by-step tutorial projects. ...
Better And Better mac版是一款集合众多优秀功能的Mac手势神器,可以帮助用户自定义的设置mac触控板所支持的手势操作,并且还支持单个应用的手势操作。BetterAndBetter Mac版除了手势快捷设定和操作以外,还兼有显示...
The root cause for this confusion is that the term botnet size is currently poorly defined. We elucidate this issue by presenting different metrics for counting botnet membership and show that they ...
Better Fog是一种后处理效果,提供了多种功能,可以制作从现实到风格化的多种外观和风格。这种效果不是一种体积解决方案,可确保最佳性能。它还包括其他功能,如平面或球体分析世界雾、自定义雾粒子着色器等。使用...
100 Skills to Better Python 100 Skills to Better Python
Better Explained Math,更好的解释(数学篇),中文; Bettern Explained Math/calculus两本英文。
unity武器拖尾效果插件 Better Trails v1.5;unity武器拖尾效果插件 Better Trails v1.5