[BOJ] 4195 : Virtual Friends - travelbeeee

문제 : https://www.acmicpc.net/problem/4195

---

[ 알고리즘풀이 ]

 Union-Find 와 자료구조 Map을 이용하면 문제를 해결할 수 있습니다. 이름이 Input 으로 들어오면, Map에 없다면 <이름, 번호>를 Map에 Insert 해주고 이 번호를 이용해 Union-Find를 하면 된다. 집합의 크기를 출력해줘야되므로, 그냥 유파가 아닌 WeightedUnion-Find 기법을 활용했다.

#include<iostream>
#include<map>
#include<string>
#include<cstring>

using namespace std;

int p[100000];

int find(int num) {
	if (p[num] < 0)
		return num;
	return p[num] = find(p[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return;

	if (p[pNum1] < p[pNum2]) { // i 가 더 많음.
		p[pNum1] = p[pNum1] + p[pNum2];
		p[pNum2] = pNum1;
	}
	else{
		p[pNum2] = p[pNum1] + p[pNum2];
		p[pNum1] = pNum2;
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		memset(p, -1, sizeof(p));

		int F;
		cin >> F;
		int count = 0;
		map<string, int> list;
		string input1, input2;
		for (int i = 0; i < F; i++) {
			cin >> input1 >> input2;
			if (list.count(input1) == 0) {
				list.insert({ input1, count });
				count++;
			}
			if (list.count(input2) == 0) {
				list.insert({ input2, count });
				count++;
			}
			merge(list.find(input1)->second, list.find(input2)->second);
			cout << -p[find(list.find(input1)->second)] << '\n';
		}
	}
	return 0;
}

---