[백준][4195][C++] 친구 네트워크

링크

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

4195번: 친구 네트워크

해설

1717 집합의 표현 문제와 상당히 유사한 문제입니다.

 

다만 차이점은 노드 구별자가 숫자가 아니라 최대 20길이의 대소문자 문자열 이기 때문에 해슁이 필요합니다.

 

직접 해쉬를 구현할 수도 있으나 그와 비슷한 역할을 할 수 있는 STL map 을 사용해서 풀었습니다.

 

map 을 사용하는것 이외에는 1717 번 문제와 똑같으므로 따로 해설은 적지 않았습니다.

 

코드

#include <iostream>
#include <map>
using namespace std;

typedef struct {
	string name;
	int num;
} parent;

map<string, parent> TABLE;
int T, F;

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

	cin >> T;
	for (int test_case = 0; test_case < T; ++test_case) {
		cin >> F;
		TABLE.clear();
		for (int i = 0; i < F; ++i) {
			string left, right;
			cin >> left >> right;

			if (TABLE.find(left) == TABLE.end()) {
				TABLE.insert({ left, { left, 1 } });
			}
			if (TABLE.find(right) == TABLE.end()) {
				TABLE.insert({ right, { right, 1 } });
			}

			while (left != TABLE[left].name)
				left = TABLE[left].name;

			while (right != TABLE[right].name) {
				string name = TABLE[right].name;
				TABLE[right].name = left;
				right = name;
			}
			if (left != right) {
				TABLE[right].name = left;
				TABLE[left].num += TABLE[right].num;
			}
			cout << TABLE[left].num << "\n";
		}
	}

	return 0;
}