Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.