UVa 10583 - Ubiquitous Religions

uva-10583.cpp

#include <cstdio>

using namespace std;

int p[50000], N;

int Find(int x) {
  if(x == p[x]) return x;
  return p[x] = Find(p[x]);
}

void Union(int x, int y) {
  x = Find(x);
  y = Find(y);
  if(x != y) {
    p[x] = y;
    --N;
  }
}

int main(void) {
  int n, m, Case = 0;
  while(scanf("%d %d", &n, &m) && (n || m)) {
    N = n;
    int x, y;
    for(int i=1; i<=n; ++i)
      p[i] = i;
    for(int i=0; i<m; ++i) {
      scanf("%d %d", &x, &y);
      Union(x, y);
    }
    printf("Case %d: %d\n", ++Case, N);
  }
  return 0;
}