코드 복사/붙여넣기 하는 당신이 아름답습니다.

4195 : 친구 네트워크

풀이

새로운 친구들이 추가될 때 마다 merge를 해주자!

모든 노드에 대해 해당 원소가 속한 네트워크의 크기를 미리 구해두고

merge 할 때 합쳐주자!

이 문제에서는 map을 쓰면 편하게 구현할 수 있다.

unordered_map을 사용하면 map보다 빠르게 구현할 수 있다.

자세한 건 cpp 레퍼런스를 참고하자.

코드

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

const int n_ = 1e5 + 1;
int pnt[n_ * 2], cnt[n_ * 2];

int find(int u) {
	if (u == pnt[u]) return u;
	return pnt[u] = find(pnt[u]);
}

int merge(int u, int v) {
	u = find(u), v = find(v);
	if (u > v) swap(u, v);
	if (u != v) {
		pnt[v] = u;
		cnt[u] += cnt[v];
		cnt[v] = 1;
	}
	return cnt[u];
}

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		int n, i, num = 1;
		char wookje[22], jehoon[22];
		unordered_map<string, int> happy;
		scanf("%d\n", &n); 
		for (i = 1; i <= 2 * n + 1; i++) pnt[i] = i, cnt[i] = 1;
		while (n--) {
			scanf("%s %s", wookje, jehoon);
			if (!happy.count(wookje)) happy[wookje] = num++;
			if (!happy.count(jehoon)) happy[jehoon] = num++;
			printf("%d\n", merge(happy[wookje], happy[jehoon]));
		}
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-17 20:11

Read more posts by this author