UVA 10685 - Nature(cpp file)

Problem Type : Disjoint Set Data Structure


#include<stdio.h>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#define MAX 50005
using namespace std;
map<string,long >mymap;
long par[MAX],node,edge,store[MAX];
void make_set()
{
    long i;
    for(i=1; i<=node; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n];
}
void Union(long x,long y)
{
    long ux,uy;
    ux= find_set(x);
    uy= find_set(y);
    if(ux!=uy)
    {
        par[ux]=uy;
    }
    else
        return;
}
int main()
{
    long i,j,n,ux,uy;
    string s,p,q;
    while(scanf("%ld %ld",&node,&edge)==2)
    {
        if(node==0 && edge==0)
            break;
        n=0;
        for(i=1; i<=node; i++)
        {
            n++;
            cin >> s;
            mymap[s]=n;
            // printf("%ld",n);

        }
        make_set();
        for(i=1; i<=edge; i++)
        {
            cin >> p >>q;
            long int x = mymap[p];
            long int y= mymap[q];
            Union(x,y);
        }
        long j=0;
        for(i=1; i<=node; i++)
        {
            store[j] =find_set(i);
            j++;
        }
        sort(store,store+j);
        long sum=0,cou,k;
        for(i=0; i<j-1; i++)
        {
            cou=1;
            for(k=i+1;k<j;k++)
            {
                if(store[i]==store[k])
                {
                    cou++;
                }
                else
                {
                    break;
                }
            }
            if(sum<cou)
            {
                sum=cou;
            }
            i=k-1;
        }
        printf("%ld\n",sum);

    }

}