BOJ 4195 친구 네트워크

1 개요

BOJ 4195 친구 네트워크

• 백준 온라인 저지 4195번 문제
• BOJ 36단계

2 C++

#include <bits/stdc++.h>
using namespace std;

#define SIZE 200000
int parent[SIZE];
int friends[SIZE];

int Find(int node) {
    if(node == parent[node]) return node;
    return Find(parent[node]);
}

void Union(int node1, int node2) {
    node1 = Find(node1);
    node2 = Find(node2);
    if(node1 != node2) {
        if(friends[node1] < friends[node2]) {
            swap(node1, node2);
        }
        parent[node2] = node1;
        friends[node1] += friends[node2];
        friends[node2] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T, F;
    cin >> T;
    while(T--) {
        cin >> F;
        int index = 0;
        for(int i=0; i<SIZE; i++) {
            parent[i] = i;
            friends[i] = 1;
        }
        string name1, name2;
        int found1, found2;
        map<string, int> m;
        for(int i=0; i<F; i++) {
            cin >> name1 >> name2;
            if(m.find(name1) == m.end()) {
                m[name1] = index;
                index++;
            }
            if(m.find(name2) == m.end()) {
                m[name2] = index;
                index++;
            }
            found1 = Find(m[name1]);
            found2 = Find(m[name2]);
            if(found1 != found2) {
                Union(found1, found2);
            }
            cout << max(friends[found1], friends[found2]) << '\n';
        }
    }
}