백준 4195번, 친구 네트워크 풀이

문제

백준 4195번

풀이

Union Find를 구현하여 해당 집합에 몇 개의 원소가 속하는지는 개수를 관리하는 배열을 하나 더 만들어주면 됩니다.

관리해야 할 원소가 string이여서 까다롭기 때문에 이 문제가 Gold II(solved 기준)이지 않을까 생각합니다.

 

C++에서는 unordered_map이라는 자료구조를 사용하여 $ mp[string] = int $라고 두면, 이론상 $ O(1) $로 각 유저의 string에 대해서 UF의 원소 int를 가져올 수 있습니다. (unordered_map<string, int> mp)

 

map이 마음에 안든다 싶으면.. set<string> 등으로 이진 탐색을 사용하는 $ O(log N) $짜리 테이블도 만들 수 있을 것 같습니다.

 

 

UF에서 개수를 구하는 구현은 코드가 쉽기 때문에 설명은 생략합니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, int> mp;
int UF[200000], unc[200000];

int find(int a) {
	return UF[a] = a == UF[a] ? a : find(UF[a]);
}

void merge(int a, int b) {
	int x = find(a), y = find(b);
	if (x == y) return;
	UF[x] = y;
	unc[y] += unc[x];
	unc[x] = 0;
}

void init(int size) {
	mp.clear();
	//한 줄에 사람이 2명이기 때문에 N*2만큼 초기화
	for (int i = 0; i < size * 2; i++) {
		UF[i] = i;
		unc[i] = 1;
	}
}

int getIdFromName(string &name) {
	return mp[name] = !mp[name] ? mp.size() : mp[name];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
		int f; cin >> f;
		init(f);

		while (f--) {
			string a, b; cin >> a >> b;
			int x = getIdFromName(a), y = getIdFromName(b);
			merge(x, y);
			cout << unc[find(x)] << "\n";
		}
	}
}