Ubiquitous Religions
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.
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
題目大意
當今世界有很多不同的宗教,很難通曉他們。你有興趣找出在你的大學(xué)里有多少種不同的宗教信仰。
你知道在你的大學(xué)里有n個學(xué)生(0 < n <= 50000) 燥滑。你無法詢問每個學(xué)生的宗教信仰俯抖。此外,許多學(xué)生不想說出他們的信仰臂容。避免這些問題的一個方法是問m(0 <= m <= n(n - 1)/ 2)對學(xué)生, 問他們是否信仰相同的宗教( 例如他們可能知道他們兩個是否去了相同的教堂) 嗅剖。在這個數(shù)據(jù)中,你可能不知道每個人信仰的宗教忆蚀，但你可以知道校園里最多可能有多少個不同的宗教矾利。假定每個學(xué)生最多信仰一個宗教。
Input
第一行第一個數(shù)字代表宗教總數(shù)馋袜，第二個為組數(shù)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 50000;
int fa[N], deep[N];
void init()
{
memset(fa, -1, sizeof(fa));
memset(deep, 0, sizeof(deep));
}
int find(int x)
{
if (fa[x] == -1) return x;
return fa[x] = find(fa[x]);
}
void unite(int x, int y)
{
x = find(x);y = find(y);
if (x == y) return;
if (deep[x]<deep[y])
fa[x] = y;
else
{
fa[y] = x;
if (deep[x] = deep[y])
deep[x]++;
}
}
bool same(int x, int y)
{
return find(x) == find(y);
}
int main()
{
int n, m;//n個宗教 m組
int x, y;//學(xué)生x 學(xué)生y
int fx, fy;//學(xué)生x y的父節(jié)點
int c = 1;//case 計數(shù)
while (scanf_s("%d%d", &n, &m) && n != 0 && m != 0)
{
init();//初始化
while (m--) {
scanf_s("%d%d", &x, &y);
fx = find(x), fy = find(y);//設(shè)置x y的父節(jié)點
if (fx!=fy) //如果父節(jié)點不相等 則合并
{
unite(fx, fy);
n--; //宗教數(shù)-1
}
}
printf("Case %d: %d\n", c++, n);
}
return 0;
}
