612 최소신장트리

신장트리 : 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 없는 그래프
크루스칼은 최소신장트리(mst)를 구할때 사용함

크리스칼 알고리즘을 이용!!
정렬 기준이 edge이다!!

최소신장트리로 분할할라면 최소신장트리를하나만들고 젤큰간선을 없애면된다

$O(ElogE)$
예로 다리를 최소한의 비용으로 놓아야하지만 다 놓아야할 때

1. 간선을 비용에 따라 오름차순으로 정렬한다
2. 사이클발생하는지 확인하고 발생하지 않을 시 mst에 포함시킨다.
   • 이때 unionfind

# 입력형식 a,b,c
# 저장형식 edges.append((c,a,b)) 비용을 앞으로
# node 개수 v
parent = [0] * (v+1)
sum_cost = 0
edges.sort()

def find_parent(parent,n):
    if parent[n] != n:
        parent[n] = find_parent(parent,parent[n])
    return parent[n]


for e in edges:
    c , a,b = e
    pa = find_parent(parent,a)
    pb = find_parent(parent,b)
    if pa != pb:
        sum_cost += c
        # 루트노드의 부모끼리 연결해야함
        if pa < pb:
            parent[pb] = pa
        else:
            parent[pa] = pb