union-find 알고리즘(파이썬 코드)

#union-find

#disjoint-set algorithm : 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

def getParent(parent, num):

    if parent[num] == num :

    return num

    else :

    return getParent(parent, parent[num])

#각 부모 노드를 합친다.

def unionParent(parent, num1, num2):

    a = getParent(parent, num1)

    b = getParent(parent, num2)

    #각 원소의 부모 동일 유무 체크

    if a == b:

        return

    else:

    if a < b:

    parent[b] = a

    else:

    parent[a] = b

    #두 set의 root 중 하나를 다른 root에 붙인다.

#같은 부모 노드를 가지는지 확인한다.

def findParent(parent, num1, num2):

    a = getParent(parent, num1)

    b = getParent(parent, num2)

    if a == b :

    return 1

    elif a != b :

    return 0

#main

parent = [0]

for i in range(1,11):

    parent.append(i)

unionParent(parent, 1, 2)

unionParent(parent, 2, 3)

unionParent(parent, 3, 4)

unionParent(parent, 5, 6)

unionParent(parent, 6, 7)

unionParent(parent, 7, 8)

print('1과 5는 연결되어 있나요? %d' % findParent(parent, 1, 5))

unionParent(parent, 1, 5)

print('1과 5는 연결되어 있나요? %d' % findParent(parent, 1, 5))

for i in range(1,11):

    print(parent[i])