백준 #4195 친구 네트워크


BOJ #4195 - 친구 네트워크

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

# 문제 분류

Disjoint Set

풀이 접근 방법


union-find + rank 쓰면 되는 문제. map을 이용해서 이름마다 번호를 부여하고 그 번호를 유니온 파인드 시키면 깔끔하게 해결할 수 있는 문제


#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>

#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, F;
string s, tmp;

int p[200010];

int find(int n) {
    if (p[n] < 0)
        return n;
    p[n] = find(p[n]);
    return p[n];
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    p[a] += p[b];
    p[b] = a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    fup(_, 1, N, 1) {
        cin >> F;
        map<string, int> who;
        fill(p, p + 200010, -1);
        fup(i, 1, F, 1) {
            cin >> s >> tmp;
            if (who.find(s) == who.end()) {
                who[s] = 2 * i - 1;
            }
            if (who.find(tmp) == who.end()) {
                who[tmp] = 2 * i;
            }
            merge(who[s], who[tmp]);
            cout << -p[find(who[s])] << endl;
        }
    }
}