Ubiquitous Religions 并查集

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;
}