Ubiquitous Religions
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 20788 | Accepted: 10212 |
Description
There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.
You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.
You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.
Input
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.
Output
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.
Sample Input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
Sample Output
Case 1: 1
Case 2: 7
Hint
Huge input, scanf is recommended.
题意:
相关推荐
Stefan Poslad编著的Ubiquitous Computing原版PDF书籍 下载于http://onlinelibrary.wiley.com 书籍的信息请参见http://www.elec.qmul.ac.uk/people/stefan/ubicom
Advances in Computer Science and Ubiquitous Computing
B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and nnplemented using B-...
Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
LNEE publishes authored monographs and contributed volumes which present cutting edge research information as well as new perspectives on classical fields, while maintaining Springer's high standards ...
普适计算与移动计算教材Ubiquitous Computing PPT slides
Asterisk with IPv6 Seamless and Ubiquitous VoIP
内容很详细,包括各个平台的开发语言都列出来,不过没有源码。有兴趣的朋友可以参考这个survey上给出的项目自己再去细细研究,读Paper,看源码。
Abstract The vision of ubiquitous computing is becoming a reality thanks to the advent of portable devices and the advances in wireless networking technologies. It aims to facilitate user tasks ...
The authors identify two key characteristics of ubiquitous computing systems, physical integration and spontaneous interoperation. They examine how these properties affect the design of ubicomp ...
商业普适计算(Ubiquitous Computing for Business) 在全年365天、每周七天、每天廿四小时全球范围内找到新市场、建立更好的业务、获得客户 (Find New Markets, Create Better Businesses, and Reach Customers ...
Evolution Toward Artificial Intelligence of Things Under 6G Ubiquitous⁃X.pdf
MATLAB.-.A.Ubiquitous.Tool.for.the.Practical.Engineer
使用智能手机和智能手表进行直观且无处不在的发热监测_Intuitive and Ubiquitous Fever Monitoring Using Smartphones and Smartwatches.pdf
CRC.Press.Cloud.Computing.Technologies.and.Strategies.of.the.Ubiquitous.Data.Center
012的一篇柔性电子的综述,主要讲述柔性电子领域的薄膜材料和技术,以及思考未来在医疗,汽车行业,人机界面,移动设备以及其他场景下的可能应用
泛在学习应用模式设计与研究,潘峰,杨旭,综述文章:随着移动互联网和普适计算技术的发展,泛在学习的出现让学习者摆脱了时间、空间和固定化学习方式的束缚,满足了课堂学
ISO IEC IEEE 18880:2015 Information technology — Ubiquitous green community control network protocol - 完整英文电子版(74页).pdf
Explore the Ubiquitous Learning on .Campus: A Friendship-Based Knowledge Diffusion Approach
java版商城源码下载 mall 说明 基于SpringBoot+MyBatis的电商系统,包括前台商城系统及后台管理系统。 如果该项目对您有帮助,您可以点右上角 "Star" 支持一下 谢谢! 或者您可以 ...一下,该项目将持续更新,不断完善...