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

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

https://www.acmicpc.net/problem/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)

from http://amaranth1ne.tistory.com/41 by ccl(A) rewrite - 2021-10-19 20:00:48