[백준] 16562번 : 친구비

16562번: 친구비

16562번: 친구비

🤔 문제분석

유니온-파인드로 문제를 해결 할 수 있습니다. 친구-친구-친구인 상태는 이미 Parent가 같은 집합들입니다. 그렇기 때문에 처음에 친구관계가 주어진다면 모두 유니온 합니다. 그런다음 친구비를 오름차순으로 정렬한뒤에 해당 친구와 유니온을 하는데, 이미 간선이 연결되어있는 상황이라면 유니온을 하지 않아야합니다. 최소신장 트리의 길이는 구하는 문제처럼 해결하면 됩니다.

💻 코드

import sys
input = sys.stdin.readline

N, M, k = map(int, input().split())

parent = [i for i in range(N+1)]

def find(v1):
    if parent[v1] != v1:
        parent[v1] = find(parent[v1])
        return parent[v1]
    
    return parent[v1]

def union(v1, v2):
    p1 = parent[v1]
    p2 = parent[v2]
    if p1 != p2:
        if p1 > p2:
            parent[p1] = p2
        else:
            parent[p2] = p1

friends = []
for i, A in enumerate(list(map(int, input().split()))):
    friends.append((A, i+1))

friends.sort(key=lambda x:x[0])

for _ in range(M):
    v, w = map(int, input().split())
    p1 = find(v)
    p2 = find(w)
    
    if p1 != p2:
        union(p1, p2)

cost = 0
for friend_be, i in friends:
    p1 = find(0)
    p2 = find(i)
    if p1 != p2:
        union(p1, p2)
        cost += friend_be

if cost > k:
    print("Oh no")
else:
    print(cost)