백준 16562 친구비 C++

 

간단한 해설

 

친구의친구는친구니깝부모의부모는부모이다즉디스조인트셋, union-parent를 사용하자.

 

N이 최대 10000이라서 union by rank를 안해도 된다.

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,k;
int parent[10001];

int findParent(int vertex){
    if(parent[vertex]!=vertex) return findParent(parent[vertex]);
    return parent[vertex];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    for(int i=1;i<=10000;++i){
        parent[i]=i;
    }
    cin>>n>>m>>k;
    vector<int> v(n+1);
    for(int i=1;i<=n;++i){
        cin>>v[i];
    }
    int a,b;
    for(int i=0;i<m;++i){
        cin>>a>>b;
        int parentA=findParent(a);
        int parentB=findParent(b);
        if(parentA!=parentB){
            //union but find more cheap chioce
            int valA=v[parentA];
            int valB=v[parentB];
            if(valA>valB){
                parent[parentA]=parentB;
            }
            else parent[parentB]=parentA;
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        int parentA=findParent(i);
        if(i==parentA){
            ans+=v[i];
        }
    }
    if(ans>k) cout<<"Oh no";
    else cout<<ans;
}