이번 문제는 유니온-파인드 알고리즘을 통해 해결하였다. 부모를 찾는 find 함수와 두 값이 연결되어 있을 때의 루트를 찾는 union 함수를 구현하고, 연결된 값 a, b를 받으면 바로바로 union함수를 통해 두 값의 루트를 찾도록 해준다. 그리고 모든 값들의 루트를 확인하여 같은 루트들 중 가장 작은 가중치를 가지는 것을 취해주도록 하면 된다. 그러나 이 풀이 방법으로 진행하였을 때 33%에서 오답 처리되었다. 다음 반례가 존재하기 때문인 것 같았다.

5 4 100
1 1 1 1 1
1 5
2 4
4 3
5 4

이 경우에 답은 1이 나와야 한다. 1-5-4-2,3 이렇게 모두 연결되어 있기 때문에 모두가 1이라는 루트를 가져야 한다. 그러나 처음에 구현한 코드로는 2개의 그룹이 만들어진다.

입력 값에 따라서 완전하게 하나의 루트를 찾지 못하는 경우가 있는 것으로 보였다. 그래서 방문처리 리스트를 이용하여 루트 리스트를 순회하고, 이 과정에서 방문하지 않은 값이 나오면 2중 for문을 통해 다시 한번 각각의 루트를 찾도록 하고, 그 루트가 둘이 같다면 두 가중치 중 더 작은 값을 가중치로 취하도록 하였다. 그리고 이 과정이 모두 끝나면 결과변수에 가중치를 더해주는 방식으로 해결하였다.

Code

n, m, k = map(int, input().split())
costs = [0] + list(map(int, input().split()))
parents = [i for i in range(n+1)]
def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)
answer = 0
visited = [False for _ in range(n+1)]
for i in range(1, n+1):
    if not visited[i]:
        tmp = [i]
        cost = costs[i]
        for j in range(1, n+1):
            if i != j:
                if find(i) == find(j):
                    tmp.append(j)
                    cost = min(cost, costs[j])
                    visited[j] = True
        answer += cost
if answer > k:
    print("Oh no")
else:
    print(answer)