Would You like to Share!

Ubiquitous Religions

Description
Thereare so many different religions in the world today that it is difficultto keep track of them all. You are interested in finding out how manydifferent 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 theirreligious beliefs. Furthermore, many students are not comfortableexpressing 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 theybelieve in the same religion (e.g. they may know if they both attendthe same church). From this data, you may not know what each personbelieves in, but you can get an idea of the upper bound of how manydifferent religions can be possibly represented on campus. You mayassume that each student subscribes to at most one religion.
Input
Theinput consists of a number of cases. Each case starts with a linespecifying the integers n and m. The next m lines each consists of twointegers i and j, specifying that students i and j believe in the samereligion. The students are numbered 1 to n. The end of input isspecified by a line in which n = m = 0.
Output
Foreach test case, print on a single line the case number (starting with1) followed by the maximum number of different religions that thestudents 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.
题目大意：
给出几个人两两之间的信仰相同；要求给出最多有多少个不同的信仰集合；
数据范围：
学生数0—50000；
边界数据：
几乎没有；
可能陷进：
几乎没有；
AC代码：
#include “stdio.h”
#include “iostream”
using namespace std;
int root[100001];
int heav[100001];
void makeset(int i)
{
root = i;
heav = 1;
}
int findset(int i)
{
if (root != i)
root = findset(root);
return root;
}
void unio(int i, int j)
{
if (heav > heav[j])
{
root[j] = i;
heav = heav + heav[j];
}
else if (heav < heav[j])
{
root = j;
heav[j] = heav + heav[j];
}
else
{
root[j] = i;
heav = heav + heav[j];
}
}
int main()
{
//freopen(”e:\\in.txt”, “r”, stdin);
int count, n;
int p, q;
int t, k;
int testcase = 0;
while(scanf(”%d%d”, &count, &n) != EOF)
{
if (count == 0 && n == 0) break;
testcase++;
for (int i = 1; i <= count; ++i)
makeset(i);
while(n–)
{
scanf(”%d%d”, &p,&q);
t = findset(p);
k = findset(q);
if (t != k)
{
count–;
unio(t, k);
}

}
printf(”Case %d: %d\n”,testcase, count);
}
return 0;
}