POJ 2524 Ubiquitous Religions（并查集）

题目链接

题意：调查学校的学生宗教信仰情况，第一行输入 n（总人数）和 m，接下来 m 行，每行两个数代表这两个人信仰共同的宗教，没人最多信仰一个宗教。问所有人最多信仰多少个宗教。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int fa[50005];
int n;
int findfa(int x){
    if(fa[x] != x){
        fa[x] = findfa(fa[x]);
    }
    return fa[x];
}

void add(int x, int y){
    if(x > y)
        swap(x, y);
    x = findfa(x);
    y = findfa(y);
    if(x != y){
        fa[y] = x;
        n--;
    }
}

int main()
{
    int m;
    int cas = 1;
    while(scanf("%d %d", &n, &m) != EOF){
        if(n == 0 && m == 0) break;
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        while(m--){
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b);
        }
        printf("Case %d: %dn", cas++, n);
    }
    return 0;
}