백준 4195 친구 네크워크 (C++)

4195번: 친구 네트워크

분리 집합을 이용한 문제이다. 먼저 입력받은 사람들의 이름이 문자열로 주어지므로 이를 set을 이용해 중복을 제거하며 모두 입력받은 후 map에 인덱스를 value로 하여 저장해주었다. 그리고 루트에 해당하는 노드를 구하는 parent와 해당 노드를 루트로 가지는 노드의 개수를 저장하는 result를 초기화 해주었다. 그 후 입력받은 관계를 차례대로 반복문을 돌면서 부모 노드를 확인하여 다를 경우 두 노드를 합쳐주고 두 노드를 부모로 하는 노드의 개수를 더해 저장해주었다. 그리고 부모 노드에 해당하는 result를 차례로 출력해주었다.
어렵지 않게 풀 수 있었던 문제였다. 분리 집합을 응용해볼 수 있었던 좋은 문제였다.

#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

int F;
vector<pair<string, string>> v;
set<string> s;
map<string, int> m;
int parent[200000];
int result[200000];

void initMap() {
	int idx = 0;
	for (auto elem : s) {
		m.insert({ elem, idx });
		idx++;
	}
}

int findParent(int a) {
	if (parent[a] == a) return a;
	else return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	if (a != b) parent[b] = a;
}

void solution() {
	initMap();

	for (int i = 0; i < s.size(); i++) {
		parent[i] = i;
		result[i] = 1;
	}

	for (int i = 0; i < v.size(); i++) {
		int a = m[v[i].first];
		int b = m[v[i].second];

		if (findParent(a) != findParent(b)) {
			int tmp = result[findParent(a)] + result[findParent(b)];
			unionParent(a, b);
			result[findParent(a)] = tmp;
		}

		cout << result[findParent(a)] << "\n";
	}
}

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

	int T;
	cin >> T;

	while (T--) {
		v.clear();
		s.clear();
		m.clear();

		cin >> F;

		string a, b;
		for (int i = 0; i < F; i++) {
			cin >> a >> b;
			v.push_back({ a,b });

			s.insert(a);
			s.insert(b);
		}

		solution();
	}
	
	return 0;
}