4195 친구 네트워크

이름이 문자열이고 최대 20글자까지라 배열로 표현하기에는 답도없어보여서 map을 사용했다.

<코드>

#include <stdio.h>
#include <string>
#include <map>
using namespace std;
 
int v[200001], gc[200001];
int c;
char a[22], b[22];
 
int f(int x) {
    return x == v[x] ? x : v[x] = f(v[x]);
}
 
int u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x != y) {
        v[y] = x;
        gc[x] += gc[y];
        gc[y] = 1;
    }
    return gc[x];
}
 
int main() {
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        int F, cnt = 0;
        map<string, int> m;
        scanf("%d", &F);
        for (int i = 0; i < 2*F; i++) v[i] = i, gc[i] = 1;
        while (F--) {
            scanf(" %s %s", &a, &b);
            if (!m.count(a)) m[a]=cnt++;
            if (!m.count(b)) m[b]=cnt++;
            printf("%d\n", u(m[a], m[b]));
        }
    }
    return 0;
}