[모각코] 210818 Today I Learned

<백준 6497번 - 전력난>

 

크루스칼 공부할 때 코드 외운다고 해놓고 안 외웠더니 오늘도 고생 좀 했다..

그래도 크루스칼은 find, union함수만 외우면 나름 금방 풀리는 것 같다.

이번 문제는 테스트 케이스가 여러 개 주어지는 경우가 있다는 것을 캐치하는데 오래 걸렸다.

마지막 입력값에 0 0 을 왜 하나 싶었는데 다 그래서였구나.......

 

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

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break
    edge = []
    parent = [i for i in range(m+1)]
    ans = 0

    for i in range(n):
        x, y, z = map(int, input().split())
        edge.append((x, y, z)) #z: 가중치

    edge.sort(key=lambda x:x[2])

    for i in edge:
        x, y, z = i
        if find(x) != find(y):
            union(x, y)
        else:
            ans += z
    print(ans)