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

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 并查集