[Python] 백준 1922번 - 네트워크 연결

문제 https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

이번 주 MST 스터디에서 1197번은 프림으로, 1922번은 크루스칼로 풀 생각이었는데

보통 문제 풀 때는 거의 다 크루스칼로 푸니까 둘 다 크루스칼로 풀기로 스터디원이랑 협의했다.

그랬더니.. 1197번이랑 입력 부분 빼고 코드가 전부 똑같다.

이번 주는 크루스칼에 익숙해지는 주간..

 

import sys
input = sys.stdin.readline

def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

n = int(input())
m = int(input())
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    edge.append([c, a, b])

edge.sort(key=lambda x:x[0])
parent= [i for i in range(n+1)]
count = 0
MST = 0

for i in range(m):
    weight = edge[i][0]
    start = edge[i][1]
    end = edge[i][2]
    if find(start) != find(end):
        union(start, end)
        MST += weight
        count += 1
    if count == n-1:
        break
print(MST)