UVa problem solution 10685 - Nature

problem link:

Discuss: you can simply solve this problem using disjoint set. just rank the set by counting the number of element in the set. and you can also use map for using number instead of string. and there is no tricky part in this problem.

try yourself before see the code




#include<bits/stdc++.h>
using namespace std;
int ara[5010],r,ran[5010];
int fnd(int u)
{
    if(u==ara[u])
        return u;
    else
       return ara[u]=fnd(ara[u]);
}
int makeUnion(int a,int b)
{
    int x=fnd(a);
    int y=fnd(b);
    if(x!=y)
    {
        for(int i=0;i<=r;i++)
        {
            if(ara[i]==y)
            {
                ara[y]=x;

            }
        }
         ran[x]+=ran[y];

    }
}
int main()
{
       //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int c;
    while(cin >>r>>c)
    {
        if(r==0&&c==0)
            break;

        map<string,int>mp;
        map<string,int>::iterator it;
        string str,s1;
        int n,i,j,cnt=0,flag=0,a,b;
        j=1;
        for(i=0;i<=r+5;i++)
        {
            ara[i]=i;
            ran[i]=1;
        }
        for(i=0;i<r;i++)
        {
            cin >>str;
            {
                it=mp.find(str);
                if(it==mp.end())
                {
                    mp[str]=j;

                  //  cout <<str<<' '<<j<<endl;
                    j++;
                }
            }

        }
        for(i=0;i<c;i++)
        {
            cin >>str>>s1;
            a=mp.find(str)->second;
            b=mp.find(s1)->second;
           // cout <<a<<' '<<b<<endl;
            makeUnion(a,b);

        }
        for(i=0;i<r;i++)

        {

            for(j=0;j<r-i;j++)

            {

                if(ran[j]<ran[j+1])
                    swap(ran[j],ran[j+1]);

            }

        }

            cout <<ran[0]<<endl;

    }
    return 0;
}