4195번: Virtual Friends

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

union-find를 이용해 친구 관계를 관리한다.

시간복잡도는 테스트 케이스마다 $O(f\lg f)$

#include<cstdio>
#include<string>
#include<map>
using namespace std;
int t, f, p[200001], sz[200001];
char a[21], b[21];
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &f);
        map<string, int> mp;
        for (int i = 0, c = 0; i < f; i++) {
            scanf("%s%s", a, b);
            if (!mp[a]) mp[a] = ++c, p[c] = c, sz[c] = 1;
            if (!mp[b]) mp[b] = ++c, p[c] = c, sz[c] = 1;
            int ra = par(mp[a]), rb = par(mp[b]);
            if (ra^rb) sz[ra] += sz[rb], p[rb] = ra;
            printf("%d\n", sz[ra]);
        }
    }
    return 0;
}