백준 소스코드 [C++] 4195 친구 네트워크

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

백준 소스코드 [C++] 4195 친구 네트워크

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int anc[200001], cnt[200001];

int getRoot(int x) {
	if (x == anc[x]) return x;
	return anc[x] = getRoot(anc[x]);
}

int merge(int L,int R) {
	L = getRoot(L);
	R = getRoot(R);
	
	if (L == R) return cnt[R];
	else
	{
		if (cnt[L] > cnt[R]) {
			anc[L] = R;
			cnt[R] += cnt[L];
			return cnt[R];
		}
		else {
			anc[R] = L;
			cnt[L] += cnt[R];
			return cnt[L];
		}
	}
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		unordered_map<string, int> hash;
		int chk = 0;
		for (int i = 0;i < 2 * n;i++) {
			anc[i] = i; cnt[i] = 1;
		}

		for (int i = 0;i < n;i++) {
			string a, b;
			cin >> a >> b;
			if (hash.count(a) == 0) hash.insert({ a, chk++ });
			if (hash.count(b) == 0) hash.insert({ b, chk++ });
			cout << merge(hash[a], hash[b]) << '\n';
		}
	}
	return 0;
}