친구비 [백준 16562]

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

 

 

from collections import deque 
n, m, k = map(int ,input().split())
arr = [0] + list(map(int, input().split()))
gra = [[] for _ in range(n+1)] 

for _ in range(m):
    a, b = map(int, input().split())
    if a != b:
        gra[a].append(b)
        gra[b].append(a)
        
visit = [0 for _ in range(n+1)]

def bfs(start):
    q = deque()
    q.append(start)
    visit[start] = 1
    min_cost = arr[start]
    
    while q:
        now = q.popleft()
        for nxt in gra[now]:
            if not visit[nxt]:
                visit[nxt] = 1
                min_cost = min(min_cost, arr[nxt])
                q.append(nxt)
    
    return min_cost

total_cost = 0
for i in range(1, n+1):
    if not visit[i]:
        total_cost += bfs(i)

if total_cost <= k:
    print(total_cost)
else:
    print("Oh no")