최소 비용 신장 트리에서 두 정점을 잇는 간선을 추가할 때 사이클이 생기는지 검사할 수 있다.

정점을 V, 간선을 E 라고 할 때 각 정점의 부모 노드를 가리키는 parent 배열이 필요하다.

이 배열은 V+1 만큼의 길이가 필요하다.(0번 노드는 없는 것이라 생각한다)

초기 parent 배열은 이렇게 정리한다.

이 때, (V, V, E) 가 다음과 같다고 가정한다

( 1, 2, 1 ) , ( 2, 3, 2 ) , ( 1, 3, 3 )

크루스칼 알고리즘을 기준으로 하면 1번 엣지가 먼저 선택된다. 이 때 위 간선들을 E를 기준으로 최소 힙으로 만들어줘야 한다.

def find(x) -> int:
    if parent[x] != x:
        parent[x] = find(parent[x]) # 경로 압축
    return parent[x]

def union(a, b):
    a_find = find(a)
    b_find = find(b)
    if a_find != b_find:
        parent[b_find] = a_find
        return True
    return False

위 코드에서 union으로 1, 2 번 정점을 검사해서 사이클이 있는지 검사한다. 현재 두 정점 모두 어디에 연결되어있지 않으므로, 부모가 자기 자신이다. 따라서 부모가 같지 않으므로 사이클이 없다.

두 정점 중 아무 정점이나 부모로 선택해도 된다 !!

union 사용 후 parent 배열은 다음과 같다.

2번 정점은 1번 노드를 부모로 가지고 있다.

다음으로 (2,3,2) 를 union으로 검사한다.

union(2,3)에서 a_find는 1, b_find는 3이다.

이 때 a_find에서 find(3)는 parent(2) ≠ 2 이므로 find(parent(2)) 를 또 호출하게 된다.

이 때는 find(1)이므로 parent(1)과 1이 같아지므로 해당 값을 리턴한다.