[BOJ] 16562 - 친구비 (Python)

 

 

아이디어

 

유니온 파인드를 이용하여 상호 배타적 집합의 개수를 구하고, 집합 내 최소 비용의 합을 구한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    for _ in range(M):
        v, w = map(int, input().split())
        union(v, w)
    for i in range(1, N+1):
        find(i)
    res = 0
    for i in set(group):
        res += A[i]
    if res <= k:
        print(res)
    else:
        print('Oh no')

def find(n):
    temp = n
    while n != group[n]:
        n = group[n]
    group[temp] = n
    return n

def union(v, w):
    v = find(v)
    w = find(w)
    if v > w:
        v, w = w, v
    group[w] = v
    if A[w] < A[v]:
        A[v] = A[w]

N, M, k = map(int, input().split())
A = [0]+list(map(int, input().split()))
group = [i for i in range(N+1)]
solution()