[파이썬, Python] 백준 14621번 : 나만 안되는 연애

백준 14621번 : 나만 안되는 연애

(문제 바로가기)

 

 

내 코드

import sys

input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())  # n : 학교의 수, m : 도로의 개수
univ = list(input().split())  # 대학교 정보 : W(여대), M(남대)
edges = []  # 학교 연결 간선 정보

for _ in range(m):
    u, v, d = map(int, input().split())
    edges.append((d, u - 1, v - 1))

edges.sort()

answer, cnt = 0, 0
parent = [i for i in range(n)]

for d, u, v in edges:
    if univ[u] != univ[v] and find_parent(parent, u) != find_parent(parent, v):
        union(parent, u, v)
        answer += d
        cnt += 1
    if cnt == n - 1:
        break
print(answer) if cnt == n - 1 else print(-1)