백준 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까?

백준 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까?

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

문제

• 링크 참조

입력

• 입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다.

• 입력의 마지막 줄에 CTP 왕국의 번호 C와 한솔 왕국의 번호 H와 추가 동맹의 기회 K(0 ≤ K ≤ 100)가 공백으로 구분되어 주어진다.

• 주어지는 입력에서 CTP 왕국과 한솔 왕국은 절대로 동맹이 되지 않게 주어진다.

출력

• CTP 왕국의 힘의 최대값을 출력

접근

• Disjoint-set과 Max heap을 활용

C++ Code

#include <cstdio>
#include <queue>
​
using namespace std;
​
int n, m;
int x, y;
int c, h, k;
​
int p[100001] = { 0, };
int cnt[100001] = { 0, };
bool pushed[100001] = { false, };
​
void init(int n) {
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        cnt[i] = 1;
    }
}
​
int parent(int who) {
    if (p[who] == who) {
        return who;
    }
​
    return p[who] = parent(p[who]);
}
​
void join(int a, int b) {
    int pa = parent(a);
    int pb = parent(b);
    if (cnt[pa] >= cnt[pb]) {
        p[pb] = pa;
        cnt[pa] += cnt[pb];
    }
    else {
        p[pa] = pb;
        cnt[pb] += cnt[pa];
    }
}
​
​
int main() {
    scanf("%d %d", &n, &m);
    init(n);
​
    while (m--) {
        scanf("%d %d", &x, &y);
​
        if (parent(x) != parent(y)) {
            join(x, y);
        }
    }
    scanf("%d %d %d", &c, &h, &k);
​
    int pc = parent(c);
    int ph = parent(h);
​
    priority_queue<int> pq;
    for (int i = 1; i <= n; i++) {
        int temp = parent(i);
        if (!pushed[temp] && temp != ph && temp != pc) {
            pq.push(cnt[temp]);
            pushed[temp] = true;
        }
    }
​
    while (k--) {
        int temp = pq.top();
        pq.pop();
​
        cnt[pc] += temp;
    }
​
    printf("%d", cnt[pc]);
​
​
    return 0;
}