1197 최소 스패닝 트리 {boj}

정렬을 할 줄이야#

모든 간선을 가중치 기준으로 정렬한 다음, 주어진 조건을 만족하기만 하면 T에 넣는다. 그렇게 총 n-1번 반복하면 된다.

주어진 조건

추가되는 간선은 사이클을 만들지 않아야 한다.

사이클 탐지방법으로는 각 노드의 부모노드가 동일한지를 검사하면 된다. Union Find 관련 블로그

def sol(G: List[Tuple[int, int, int]]) -> int:
    """
    순회를 돌면서 매번 최소 가중치 간선을 찾아 추가하는 알고리즘
    가중치값만 구하면 되므로 최소신장그래프는 작성하지 않는다.

    근데, 순환탐지를 어떻게 하지? => 간선을 추가할 때 중복된 정점이 있다면 순환임.

    근데, 중복된 정점을 어떻게 찾지? => Union Find

    - G: 연결리스트 형식의 그래프, 각 원소는 (시작 정점번호, 인접 정점번호, 가중치)로 이루어져 있다.

    """
    disjoint_set = [i for i in range(MAXV + 1)]  # 순환탐지용
    ret = 0
    G.sort(key=lambda e: e[2])

    for u, v, w in G:
        try:
            union_parent(disjoint_set, u, v)
            ret += w
        except NotADisJointSet:
            continue

    return ret