POJ 2524 Ubiquitous Religions

题目链接：POJ 2524 【Ubiquitous Religions】

思路

       经典并查集模板，求集合个数。

代码

#include <iostream>

using namespace std;
#define ll long long
const int N = 5e5 + 10;

int fa[N];
int n, m;
void init(int n) {
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
}

int find(int x) {
  if (x == fa[x])
    return x;
  else
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
  fa[find(x)] = find(y);
}

void solve(int x) {
  init(n + 10);

  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    merge(a, b);
  }

  int num = 0;
  for (int i = 1; i <= n; i++) {
    if (fa[i] == i) {
      num++;
    }
  }
  cout << "Case " << x << ": "  << num << endl;
}

int main() {
  int x = 1;
  while (cin >> n >> m) {
    if (n == 0 && m == 0)
      break;
    solve(x++);
  }
  return 0;
}