풀이
새로운 친구들이 추가될 때 마다 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이