D - Ubiquitous Religions
在三角洲不同地区生活的人们有自己信仰的图腾，为了避免冒犯到他们，首脑们现在想知道他们最多可能有多少种图腾。但这对他们来说是件无趣的事，所以现在任务交到了你的身上。 当你看到两个地区的人们在膜拜同一外观的石像时，就可以断定他们拥有同样的图腾。已知三角洲共有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
思路：
这道题其实就是一个并查集的板子题 我们需要去判断连通块一共有多少 用并查集进行数据压缩 后面简单的判断就好
AC代码
//并查集
#include<iostream>
#include<cstring>
using namespace std;
int pre[1000000];
int find(int i)
{
if(pre[i]!=i)
{
pre[i]=find(pre[i]);
}
return pre[i];
//带路径压缩
}
int m,n;
int tmpa,tmpb;
int sum;
int main()
{
while(cin >> m >> n)
{
if(m==0 && n==0) break;
memset(pre,0,sizeof(pre));
int ans=0;
for(int i=1;i<=m;i++)
pre[i]=i;
for(int i=0;i<n;i++)
{
cin >> tmpa >> tmpb;
int a=find(tmpa);
int b=find(tmpb);
if(a!=b)
pre[a]=b;
}
for(int i=1;i<=m;i++)
if(pre[i]==i)
ans++;
cout << "Case " << ++sum <<": " << ans << endl;
}
return 0;
}