10583 - Ubiquitous Religions C++ Solutions

This is the solution to this UVa problem

Code

#include <iostream>
#include <iostream>
#include<bits/stdc++.h>
#define pb push_back
#define T 50005

using namespace std;


int p[T];
int r[T];

void ini(int n){
 for(int i=0;i<n;i++){
  p[i]=i;
  r[i]=1;
  }
 }
 
int root(int a){
 while(p[a]!=a){
  
  p[a]=p[p[a]];
  a=p[a];
 }
 return a;
 }
 
void joint(int a,int b){
 if (a==b) return; 
 a=root(a);
 b=root(b);
 if (a == b) return;
 if(r[a]>r[b]){
  r[a]+=r[b];
  p[b]=a;
  return;
  }
 r[b]+=r[a];
 p[a]=b;
 }
 
bool query(int a, int b){
 return p[a]==p[b];
 }
 
 

int main() {
 std::ios::sync_with_stdio(false);
 int test=0;
 while(1){
  test++;
  int n,m;
  cin >> n>>m;
  if(n==0 && m==0) break;
  ini(n);
  while(m--){
   int i,j;
   cin>>i>>j;
   joint(i-1,j-1);  
   }
   int counter=0;
 for(int i =0;i<n;i++){
  if(root(i)==i) counter++;
  }
  cout<<"Case "<<test<<": "<<counter<<"\n";
  
  
  }
 
 
 return 0;
}