1094 - Virtual Friends

virtualfriends.cpp

#include <iostream>
#include <vector>
#include <map>
using namespace std;
char n1[21], n2[21];
int p = 1;
map<string, int> mapa;
vector<int> namistades;
vector<int> padres;

int root(int hijo){
	int padre = 0;
	
	if(padres[hijo] != hijo){
		padres[hijo] = root(padres[hijo]);
	}

	return padres[hijo];
}

int join(int i1, int i2){
	int p1 = root(i1);
	int p2 = root(i2);
	if(p1 != p2){
		padres[p1] = padres[p2];
		namistades[p2] += namistades[p1];
	}
	return namistades[p2];
}

int main(){
	int t, F;
	cin >> t;
	
	while(t--){
		cin >> F;
		namistades.clear();
		padres.clear();
		mapa.clear();
		p = 1;
		namistades.insert(namistades.end(),0);
		padres.insert(padres.end(),0);
		while(	F--){
			cin >> n1 >> n2;
			if(mapa[n1] == 0){
				mapa[n1] = p;
				padres.insert(padres.end(),p);
				namistades.insert(namistades.end(),1);
				p++;
			}
			
			if(mapa[n2] == 0){
				mapa[n2] = p;
				padres.insert(padres.end(),p);
				namistades.insert(namistades.end(),1);
				p++;
			}
			cout << join(mapa[n1],mapa[n2]) << endl;
		}
	}
	return 0;
}