11503 - Virtual Friends.cpp

#include<bits/stdc++.h>
using namespace std;

int par[200000];
int num[200000];
map<string,int>m;

int fin(int x){

    if(par[x]==x) return x;
    return par[x]=fin(par[x]);
}



int  unio(int a, int b){
    a = fin(a);
    b = fin(b);

    if(a!=b) {
    	par[a]=b;
    	num[b] += num[a];
    }
    return b;
}

int main(){



    int t;
    scanf("%d",&t);
    while(t--){


        m.clear();
        int e;
         scanf("%d",&e);

         for(int i=0;i<2*e;i++){
            par[i]=-1;
            num[i]=1;
        }

        getchar();
        int i=0;
        while(e--){



            string a,b;
            cin>>a>>b;
            int aa,bb;

            if(m.find(a)==m.end()){
                m[a]=i;
                par[i]=i;
                i++;
            }

            if(m.find(b)==m.end()){
                m[b]=i;
                par[i]=i;
                i++;
            }

            aa = m[a];
            bb = m[b];

            int c = unio(aa,bb);
            int cou=0;

            cout<<num[fin(aa)]<<"\n";


        }

    }

    return 0;

}