[4195] 친구 네트워크

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

4195번: 친구 네트워크

일단 문자열을 숫자로 바꿔놓고 생각하면 두 정수형 A, B에 대해 union(A,B)를 해준다.

p[]의 값을 트리의 크기로 놓으면, abs(find(A))가 답이 된다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

#define union _union

int n, m, p[1000005];

int find(int cur) {

    if (p[cur] < 0) return cur;

    return p[cur] = find(p[cur]);

}

void union(int A, int B) {

    A = find(A), B = find(B);

    if (A == B) return;

    if (p[A] < p[B])

        p[A] += p[B], p[B] = A;

    else

        p[B] += p[A], p[A] = B;

}

unordered_map<string, int> mp;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        memset(p, -1, sizeof(p));

        mp.clear();

        cin >> n;

        int i;

        for (i = 0; i < n; i++) {

            string a, b;

            cin >> a >> b;

            if (mp.count(a) == 0) mp[a] = 1 + mp.size();

            if (mp.count(b) == 0) mp[b] = 1 + mp.size();

            int A = mp[a], B = mp[b];

            union(A, B);

            A = find(A);

            cout << abs(p[A]) << '\n';

        }

    }

    return 0;

}

---