[SWEA] 최소신장트리

링크: 5249. [파이썬 S/W 문제해결 구현] 7일차 - 최소 신장 트리

풀이

def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]


def union(x, y):
    x = find(x)
    y = find(y)
    parent[y] = x

TC = int(input())

for test_case in range(1, TC + 1):
    v, e = map(int, input().split())  # 마지막 노드 번호, 간선 수
    graph = []
    answer = 0
    
    parent = [i for i in range(v + 1)]
    for _ in range(e):
        n1, n2, w = map(int, input().split())
        graph.append((n1, n2, w))

    graph.sort(key=lambda x: x[2])
    cnt = 0
    
    for n1, n2, w in graph:
        if find(n1) != find(n2):
            union(n1, n2)
            answer += w
            cnt += 1
        if cnt == v:
            break
            
    print(f'#{test_case} {answer}')