Description 世界上有许多不同的宗教,现在有一个你感兴趣的问题:找出多少不同的宗教, 在你的大学中的大学生信仰了多少种不同的宗教。你知道在你的大学有 n个学生(0<n<= 50000 )。若直接问每一个学生的宗教信仰不大适合。此外,许多学生还不太愿意说出自己的信仰。有一种方法来避免这个问题,询问 m(0<=m<=n (n- 1)/2)对学生,询问他们是否信仰同一个宗教(比如,可以询问他们是否都参加同一教堂)。从这个数据,您可能不知道每个人宗教信仰,但是你可以知道有多少不同宗教信仰。你可以假设,每名学生最多信仰一个宗教。 Input 输入包含多组测试数据。每组测试数据的开头包含两个整数 n和m。接下来有 m 行,每行有两个整数 i和j,编号为 i和j的同学信仰同一个宗教。学生的编号从从 1开始到 n。当输入使 n=0 ,m=0 标志输入的结束。 Output 每组测试数据的输出只有一行,包含数据的组别(从1开始)和学生最多信仰的宗教数。 Sample Input 10912131415********** 1042345485800Sample Output Case 1:1Case 2:7 C 算法描述: #include<> int stu[50001],mark[50001]; int find(int value) { if(stu[value] != value) stu[value] = find(stu[value]); return stu[value]; } void Union(int pos1,int pos2) { if(mark[pos1] > mark[pos2]) stu[pos2] = pos1; else { stu[pos1] = pos2; if
ACM宗教信仰.doc 来自淘豆网m.daumloan.com转载请标明出处.
