[백준 / C++] 4195번: 친구 네트워크

백준 4195번: 친구 네트워크
알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵, 분리 집합

백준 문제 바로가기

🤨 Hmm...

이 문제를 같은 parent를 공유하는 원소의 개수를 세면 되는 문제다.

다만 개수를 세기 위해 모든 원소에 대해서 find 연산을 수행하면 시간 초과가 발생한다.

그래서 원소의 개수를 담을 배열을 하나 더 선언하고, union 연산을 하기 전에 두 원소의 parent를 비교한다.

같으면 개수 갱신 할 필요가 없고, 다르면 한 쪽에 다른 쪽을 더해주면 된다.

💻 소스 코드

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int T, F;
    vector<int> parent;
    vector<int> count;
    map<string, int> info;
public:
    BJ();
    int findParent(int x);
    void unionParent(int x, int y);
};

BJ::BJ() {
    cin >> T;

    string x, y;
    while (T--) {
        cin >> F;
        parent.clear();
        count.clear();
        info.clear();
        int n = 0;
        while (F--) {
            cin >> x >> y;
            if (info.find(x) == info.end()) {
                info[x] = n;
                count.emplace_back(1);
                parent.emplace_back(n);
                n++;
            }
            if (info.find(y) == info.end()) {
                info[y] = n;
                count.emplace_back(1);
                parent.emplace_back(n);
                n++;
            }
            int nx = info[x], ny = info[y];
            int px = findParent(nx), py = findParent(ny);
            if (px != py) {
                count[min(px, py)] += count[max(px, py)];
            }
            unionParent(nx, ny);
            cout << count[min(px, py)] << '\n';
        }
    }
}
int BJ::findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);
    return parent[x];
}
void BJ::unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py) {
        parent[py] = px;
    }
    else {
        parent[px] = py;
    }
}

signed main(){
    fastIO;

    BJ a;
}