10583 - Ubiquitous Religions.cpp

#include<bits/stdc++.h>
using namespace std;

int n,e;
int par[50005];

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

int finder(int x){

    if(par[x]==x) return x;
    else return par[x] = finder(par[x]);

}

int main(){

        int p=1;
        while(cin>>n>>e){
            if(n==0 && e==0) break;
            makeset(n);
            int a,b;
            for(int i=0;i<e;i++){

                cin>>a>>b;

                a = finder(a);
                b = finder(b);

                if(a!=b){
                    par[a]=b;
                }

            }

            map<int,int>m;
            int j =0;

            for(int i=1;i<=n;i++){
                int k =finder(i);
                if(m.find(k) == m.end()){
                    m[k]=j;
                    j++;
                }

            }

            cout<<"Case "<<p<<": "<<j<<"\n";
            p++;
        }

}