POJ(PKU) Ubiquitous Religions

• 問題概要

学生の数(n)、クエリの数(m)が与えられる。各クエリはn以下の二つの整数があり二人の学生は同じ宗教であることを示している。
学校内で予想できる最大の宗教の数はいくつかもとめる。

• 解法

Union-Findやるだけ
自分が親であるのをカウント。

これも一発ACだった。

#include <cstdio>

using namespace std;

int par[50003];
int rank[50003];

void init(int n){
  for(int i = 1;i <= n;i++){
    par[i] = i;
    rank[i] = 0;
  }
}

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

void unite(int x,int y){
x = find(x);
y = find(y);

if(x == y)return;

if(rank[x] < rank[y]){
  par[x] = y;
}else{
  par[y] = x;
  if(rank[x] == rank[y])rank[x]++;
}
}

bool same(int x,int y){
  return find(x) == find(y);
}
  
int main(){
  
  int n,m;
  int co = 1;
  while(1){
  
  scanf("%d%d",&n,&m);
  if(n == 0)break;
  init(n);
  
  for(int i = 0;i < m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    
    unite(a,b);
  }
  
  int ans = 0;
  
  for(int i = 1;i <= n;i++){
    if(find(i) == i)ans++;
  }
  printf("Case %d: %d\n",co,ans);
  co++;
  }
  return 0;
}