문제 링크

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

문제 설명

• 친구에게 돈을 주면 친구가 되어준다
• 친구의 친구는 친구다
• 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용 출력

풀이

• 모든 노드를 돌면서 한 클러스터의 최소 비용을 구한다
• 클러스터 별 비용의 합을 구한다

코드

import sys
from collections import deque


def init():
    ipt = sys.stdin.readline
    n, m, k = map(int, ipt().split())
    cost_list = list(map(int, ipt().split()))
    adj_list = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, ipt().split())
        adj_list[a-1].append(b-1)
        adj_list[b-1].append(a-1)
    visited = [False] * n
    return n, k, visited, 0, adj_list, cost_list


def bfs(start):
    min_cost = float('inf')
    visited[start] = True
    q = deque([start])
    while q:
        cn = q.popleft()
        min_cost = min(min_cost, cost_list[cn])
        for nn in adj_list[cn]:
            if not visited[nn]:
                visited[nn] = True
                q.append(nn)
    return min_cost
    
    
n, k, visited, ans, adj_list, cost_list = init()
for i in range(n):
    if not visited[i]:
        ans += bfs(i)
if ans <= k:
    print(ans)
else:
    print('Oh no')