[python] 백준 16562 친구비

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

16562번: 친구비

문제 해결

• 결국 친구 사이클(network)를 만들어서 거기서 친구비 가장 작은 값을 더해주는 문제.
• 즉 사이클과 그 사이클 안의 가장 작은 친구비를 구하면 된다.

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize
sys.setrecursionlimit(10**6)
def dfs(num):
    global money
    money = min(money, A[num])
    if len(graph[num])==0:
        return
    for go in graph[num]:
        if visited[go] ==False:
            visited[go] = True
            dfs(go)
if __name__=='__main__':
    n, m, k = map(int, input().split()) # 학생 수, 친구 관계수, 돈
    A = [0] + list(map(int, input().split())) # 친구 비
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [False]*(n+1)
    ans = 0
    for i in range(1,n+1):
        if not(visited[i]):
            visited[i] = True
            money = INF
            dfs(i)
            ans += money
    if k >= ans:
        print(ans)
    else:
        print("Oh no")