BOJ 16562 친구비

사용한 알고리즘

Union-find

알고리즘 설명

친구의 친구는 친구가 되므로, 친구의 친구의 친구는 친구가 된다?ㅋ
이러한 형태로, 한명의 친구를 사귀면 그 친구들 모두 친구다.
친구들간의 관계를 Union-find 를 이용하여 merge한다.
merge의 root 기준은 money가 적은 사람으로 한다.
위 형태로 merge 한뒤 모든 친구를 사귀며 merge 한다.
최종 금액을 출력한다.

풀이

// baekjoon 16562 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=10001;

int N, M, K, money[MAX_N];
int root[MAX_N];
bool visited[MAX_N];

int find(int x) {
    if (!root[x]) return x;
    return root[x]=find(root[x]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (money[a] > money[b]) swap(a, b);
    root[b]=a;
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i=1; i<=N; i++)
        scanf("%d", &money[i]);

    for (int i=0; i<M; i++) {
        int v, w;
        scanf("%d%d", &v, &w);
        merge(v, w);
    }

    int need_money = 0;
    for (int i=1; i<=N; i++) {
        if (visited[find(i)]) continue;
        need_money += money[find(i)];
        visited[find(i)]=true;
    }
    if (need_money <= K) printf("%d\n", need_money);
    else printf("Oh no\n");
    return 0;
}