[백준] 1647번 도시 분할 계획 파이썬 코드

코드

# 크루스칼 알고리즘 이용

import sys
input = sys.stdin.readline

def find(a,lst):
  if a != lst[a]:
    lst[a] = find(lst[a], lst)
  return lst[a]

def union(a,b,lst):
  a = find(a,lst)
  b = find(b,lst)
  if a < b:
    lst[b] = a
  else:
    lst[a] = b

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

edge.sort(key=lambda x: x[0])
last = 0
res = 0
for i in range(m):
  cost, v1, v2 = edge[i]
  if find(v1, parent) != find(v2,parent):
    union(v1, v2, parent)
    res += cost
    last = max(last, cost)
print(res-last)