UVa problem solution 11503 - Virtual Friends

problem link:

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

try yourself, before see the code




#include<bits/stdc++.h>
using namespace std;
int ara[100010],ran[100010],j;
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)
    {

      ara[y]=x;
      ran[x]+=ran[y];
    }
    cout <<ran[x]<<endl;
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        int f,i,cnt=0,flag=0,a,b;
        string s1,s2;
        map<string,int>mp;
        map<string,int>::const_iterator it;
        cin >>f;
        j=1;
        for(i=0;i<=f+5 ;i++)
        {
            ara[i]=i;
            ran[i]=1;
        }
        for(i=0;i<f;i++)
        {
                cin >>s1>>s2;
                it=mp.find(s1);
                if(it==mp.end())
                {
                    mp[s1]=j;
                    j++;
                }
                it=mp.find(s2);
                if(it==mp.end())
                {
                    mp[s2]=j;
                    j++;
                }
                a=mp.find(s1)->second;
                b=mp.find(s2)->second;
                makeUnion(a,b);

        }

    }
    return 0;
}