백준 4195번 친구 네트워크

http://icpc.me/4195

4195번: 친구 네트워크

풀이

Union-find와 map STL을 사용해 풀었습니다.

 

사용자가 문자열 이름이 아닌 번호로 주어졌다고 가정합시다. 이러한 경우에는 Union-find로 각 사용자와 친구 네트워크의 크기를 관리하며 쉽게 풀 수 있습니다. union-find 트리를 나타낼 배열과 각 사용자의 친구 네트워크의 크기를 나타낼 배열이 필요합니다. 두 사용자가 친구 관계를 맺으면 union연산을 통해 두 사용자가 속해 있는 친구 네트워크를 합친 뒤, 친구 네트워크의 크기를 나타내는 배열의 값 또한 적절히 갱신하면 됩니다. 

 

사용자를 문자열으로 된 이름으로 구별해야 하기 때문에 각 사용자를 나타낼 번호를 직접 할당해 주어야 합니다. 사용자에게 1번부터 차례대로 번호를 할당한 뒤, 이름과 할당된 번호를 map에 묶어 저장하면 문제를 풀 수 있습니다. 

 

코드

친구 관계가 최대 100000개이므로 사용자는 최대 200000명입니다. 이를 유의하여 배열 크기를 잡아야 합니다.

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
#define all(v) v.begin(), v.end()
using namespace std;
int uf[200005], cnt[200005];
int find(int a) {
    if (!uf[a])
        return a;
    return uf[a] = find(uf[a]);
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        cnt[a] = cnt[b] = cnt[a] + cnt[b];
        uf[a] = b;
    }
}
void solve() {
    map<string, int> mp; // 닉네임 : uf 인덱스
    int n, idx = 1;
    string a, b;
    cin >> n;
    memset(uf, 0, sizeof(int) * (n + 2));
    memset(cnt, 0, sizeof(int) * (n + 2));
    while (n--) {
        cin >> a >> b;
        if (mp.find(a) == mp.end()) {
            mp.insert({ a, idx });
            cnt[idx++] = 1;
        }
        if (mp.find(b) == mp.end()) {
            mp.insert({ b, idx });
            cnt[idx++] = 1;
        }
        merge(mp[a], mp[b]);
        cout << cnt[find(mp[a])] << '\n';
    }
}
int main() {
    fast;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

 

사족

처음에는 친구 관계가 100000개라서 배열 크기를 100005로 잡았다 틀렸어요

금방 찾아서 다행이에요