11503 - Virtual Friends UVA.cpp

/**
La idea de solución es usar union-find disjont sets
combinado con un map

**/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <cstdio>
//#define gc getchar_unlocked
using namespace std;

typedef vector<int> vi;

vi P,R,S;//padres,ranking,set size

int N;//numero de conjuntos

void inicializar(int n){
    N=n;
    R.assign(N,0);
    S.assign(N,1);
    P.assign(N,0);
    for(int i=0;i<N;i++)
        P[i]=i;
}
int findSet(int x){
    return x==P[x]?x:P[x]=findSet(P[x]);
}
int isSameSet(int x, int y){
    return findSet(x)==findSet(y)?1:0;
}
void unionSet(int x, int y){
    if(!isSameSet(x,y)){
        int p1=findSet(x);
        int p2=findSet(y);
        N--;
        //para mantener corto el arbol
        if(R[p1]>R[p2]){
            P[p2]=p1;
            S[p1]+=S[p2];
        }
        else{
            P[p1]=p2;
            S[p2]+=S[p1];
            if(R[p1]==R[p2])
                R[p2]++;
        }
    }
}
/**
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}**/
int t,f;
string n1,n2;
int main(){

    scanf("%d",&t);
    while(t--){
        int indice=1;
        scanf("%d",&f);
        //a lo mas habrá 2f personas
        inicializar( (f*2)+1  );
        map <string,int> P;//personas
        while(f--){
            cin>>n1;
            cin>>n2;
            if(!P[n1])
                P[n1]=indice++;
            if(!P[n2])
                P[n2]=indice++;

            unionSet(P[n1],P[n2]);
            printf("%d\n",S[findSet(P[n1])]);
        }
    }
    return 0;

}