UVA 10583 - Ubiquitous Religions(cpp file)

Problem Type : Disjoint Set Data Structure





#include<stdio.h>
#include<string.h>
#define MAX 50000
using namespace std;
long int par[MAX],coun;
void make_set(long n)
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long int find_set(long n)
{
    if(n!=par[n])
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
void Union(long n,long m)
{
    int ux=find_set(n);
    int uy=find_set(m);
    if(ux==uy)
    {
        return;
    }
    else
    {
        coun--;
        par[ux]=uy;
    }
}
int main()
{
    long int n,m,i,j,k,node1,node2,cas=0;
    while(scanf("%ld%ld",&n,&m)&&n&&m)
    {
        cas++;
        coun=n;
        make_set(n);
        for(i=1;i<=m;i++)
        {
            scanf("%ld %ld",&node1,&node2);
            Union(node1,node2);
        }
        printf("Case %ld: %ld\n",cas,coun);
        memset(par,0,sizeof(par));

    }


}