[백준] 14621. 나만 안되는 연애

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

14621번: 나만 안되는 연애

크루스칼을 이용해 간단하게 풀 수 있다.

만약 해당 노드끼리 성별이 같으면 continue로 넘어가주고, 성별이 다르다면 이어준다.

edge_num으로 이어진 간선의 개수를 세어주고, 중간에 모든 정점이 이어지면 break를 해준다. 만약 주어진 간선을 이용해 정점을 이었는데도 모든 정점이 이어지지 않았다면 edge_num의 개수를 체크하여 -1, 모두 이어졌다면 경로의 길이를 출력한다.

import sys
input = sys.stdin.readline


def find_p(x):
    if x != p[x]:
        p[x] = find_p(p[x])
        return p[x]
    else:
        return x


N, M = map(int, input().split())
university = list(input().split())
input_list = []
p = [i for i in range(N)]
for _ in range(M):
    u, v, d = map(int, input().split())
    input_list.append([u-1, v-1, d])

input_list.sort(key=lambda x:x[2])
ans = 0
edge_num = 0

for i in range(M):
    u, v, d = input_list[i]

    if university[u] == university[v]:
        continue
    else:
        p1 = find_p(u)
        p2 = find_p(v)
        if p1 == p2:
            continue
        else:
            p[p1] = p2
            ans += d
            edge_num += 1
    if edge_num == N - 1:
        break

if edge_num == N - 1:
    print(ans)
else:
    print(-1)