[BOJ] 16562번: 친구비

문제 링크:

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

접근법:

모든 컴포넌트를 탐색하며 컴포넌트에 포함된 가장 작은 비용을 선택하여 모두 합하면 된다.
합한 비용이 가지고 있는 돈보다 적으면 Oh no를 출력하면 된다.

코드:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N, M, k, A[10001], v, w, visited[10001], cnt, ans;
vector<vector<int>> f;

int dfs(int curr){
    cnt++;
    int ret = A[curr];
    visited[curr] = true;
    for(int next : f[curr]){
        if(visited[next]) continue;
        ret = min(ret, dfs(next));
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> k;
    for(int i = 0; i < N; i++)
        cin >> A[i];
    f = vector<vector<int>>(N);
    for(int i = 0; i < M; i++){
        cin >> v >> w;
        v--, w--;
        f[v].push_back(w);
        f[w].push_back(v);
    }
    for(int i = 0; i < N; i++)
        if(!visited[i])
            ans += dfs(i);
    if(cnt != N || k < ans){
        cout << "Oh no";
        return 0;
    }else{
        cout << ans;
    }
}