UVA 11503 - Virtual Friends

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int rx[1000001], p[1000001];
map<string,int> R;

int findF(int x)
{
   return p[x] == x ? x : (p[x]=findF(p[x]));
}

int makeFriend(int x, int y)
{
    int u = findF(x);
    int v = findF(y);
    if(u!=v)
    {
        if(rx[u] > rx[v])
        {
            rx[u] += rx[v];
            p[v]=u;
            return rx[u];
        }
        rx[v] += rx[u];
        p[u] = v;
        return rx[v];
    }

    return rx[u];
}


int main()
{

  int test,n,tx,ty;
  char x[30], y[30];

  sc("%d",&test);

  while(test--)
  {
      sc("%d",&n);
      int cnt =0;
      for(int i=0 ; i<=min(2*n,100000) ; i++)
      {
          p[i] =i;
          rx[i]=1;
      }

      while(n--)
      {
         sc("%s %s",&x,&y);
         tx = R[x];
         ty = R[y];
         if(tx==0)
         {
             R[x] = ++cnt;
             tx = cnt;
             //pf("#%d\n",cnt);
         }
         if(ty==0)
         {
             R[y] = ++cnt;
             ty = cnt;
              //pf("#%d\n",cnt);
         }

         pf("%d\n",makeFriend(tx,ty));

      }

      R.clear();
  }

    return 0;
}