1.题目

北理CS学院2015级的学长学姐们终于搬到村里了，他们住进了新的宿舍，你想知道学校给CS学院一共安排了多少宿舍，但矜持的学长学姐们是不会直接告诉你他们宿舍号的，你唯一机会是当看到两位学姐相伴而行或者两位学长相依为Gay的时候，就可以断定他们住在同一间宿舍。已知CS学院2015级共有n(n <= 50000)名同学，你看到了m(m<=n(n-1)/2)组学长学姐对，现在请问他们至多住进了多少间宿舍。
Input
有多组数据。对于每组数据：
第一行：两个整数n和m。
以下m行：每行包含两个整数i和j，表示推断i和j住在同一间宿舍。学生编号从1到n。
输入的最后一行中,n = m = 0。
Output
对于每组测试数据，输出一行，输出数据序号( 从1开始) 和宿舍的最大数量。（参见样例）
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.

2.思路

简单的并查集。

3.代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5e4 + 10;
int Rank[maxn], Fa[maxn];
void init(int n)//初始化
{
	for (int i = 1; i <= n; i++)
	{
		Fa[i] = i;
		Rank[i] = 1;
	}
}
int find(int x)//查找
{
	return x == Fa[x] ? x : (Fa[x] = find(Fa[x]));//路径压缩
}
void merge(int i, int j)
{
	int x = find(i), y = find(j);
	if (Rank[x] <= Rank[y])
	{
		Fa[x] = y;
	}
	else
	{
		Fa[y] = x;
	}
	if (Rank[x] == Rank[y] && x != y)
	{
		Rank[y]++;
	}
}
int main()
{
	int n,m,cas=0;
	while (cin >> n >> m)
	{
		if (n == 0 && m == 0) break;
		init(n);
		while (m--)
		{
			int x, y;
			cin >> x >> y;
			merge(x, y);
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			if (Fa[i] == i)/// 统计一共产生多少个集合
			{
				cnt++;
			}
		}
		printf("Case %d: %d\n", ++cas,cnt);		
	}
	return 0;
}