11503 - Virtual Friends

#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<map>
#include<iostream>
#define MAX 100005

using namespace std;

map<string,long >mymap;
long  par[MAX];
long  arr[MAX];

long khoj_rep(long r)
{
    if(par[r]==r)
    {
        return r;
    }
    else
    {
        return (par[r]=khoj_rep(par[r]));
    }
}

main()
{
    long test,koyta_pair,i,incr,u,v,x,U,V;
    string s,s1;
    cin>>test;
    while(test--)
    {
        cin>>koyta_pair;
        incr=0;
        mymap.clear();
        for(x=1; x<=koyta_pair; x++)
        {
            cin>>s>>s1;
            if(mymap.find(s)==mymap.end())
            {
                mymap[s]=++incr;
                u=incr;
                par[u]=u;
                arr[u]=1;

            }
            if(mymap.find(s1)==mymap.end())
            {
                mymap[s1]=++incr;
                v=incr;
                par[v]=v;
                arr[v]=1;
            }

            U=khoj_rep(mymap[s]);
            V=khoj_rep(mymap[s1]);


            if(U!=V)
            {
                par[U]=V;
                arr[V]+=arr[U];
                cout<<arr[V]<<endl;
            }
            else
            cout<<arr[V]<<endl;
        }
        memset(arr,0,sizeof(arr));
    }
    return 0;
}