[BOJ/백준] 1922 네트워크 연결 파이썬

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

1922번: 네트워크 연결

MST 문제이다. 다른 변형 없이 크루스칼 알고리즘으로 풀면 된다.

이때 사이클 체크는 유니온-파인드 알고리즘으로 해결하면 된다.

이때 파인드 과정에 경로 압축을 수행하자.

from sys import stdin

input = stdin.readline

n = int(input())
m = int(input())

edges = [tuple(map(int, input().split())) for _ in range(m)]
edges.sort(key=lambda x:x[2])
parent = [i for i in range(n+1)]

def solv():
    print(kruskal())
def kruskal():
    edge_count = 0
    cost = 0
    for a,b,c in edges:
        if not is_same_parent(a,b):
            union(a,b)
            cost += c
            edge_count += 1
            if edge_count == n-1:
                return cost
def find(target):
    global parent
    if parent[target] == target:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    global parent
    a = find(a)
    b = find(b)

    if a != b:
        if a > b:
            parent[a] = b
        else:
            parent[b] = a

def is_same_parent(a,b):
    return find(a) == find(b)
solv()