[UVa] 10583 Ubiquitous Religions.cpp

#include <cstdio>
#include <set>
using namespace std;

int Set[50010];
int nOfReligion;

void Set_Initial(int N);
int FindRoot(int x);
void Union(int x, int y);

int main()
{
    int N, M, Case = 1;
    while (scanf("%d %d", &N, &M) && (N || M)) {

        Set_Initial(N);
        int x, y;
        nOfReligion = N;

        while (M--) {
            scanf("%d%d", &x, &y);
            Union(x, y);
        }
        printf("Case %d: %d\n", Case++, nOfReligion);
    }
    return 0;
}
void Set_Initial(int N)
{
    for (int i = 1; i <= N; ++i)
        Set[i] = i;
}
int FindRoot(int x)
{
    if (x == Set[x])
        return x;
    return Set[x] = FindRoot(Set[x]);
}
void Union(int x, int y)
{
    x = FindRoot(x);
    y = FindRoot(y);

    if (x != y) {
        Set[x] = y;
        --nOfReligion;
    }
}