Algorithm | Union-Find

그래프 알고리즘 Union-Find

*나동빈-실전 알고리즘 강좌 정리노트입니다

Union-Find는 대표적인 그래프 알고리즘 (합집합 찾기 알고리즘)
여러개의 노드가 존재할 때 두개의 노드를 선택해 현재 두 노드가 서로 같은 그래프에 속하는지를 판별

• Find : 어떤 집합에 포함되어 있는지 찾는 연산
• Union : 두 개의 노드를 합치는 연산

1. 각 노드의 부모노드는 자기자신

2. Union(1, 2) : 1과 2노드를 합침!
2의 부모노드가 1로 갱신

# 부모 노드를 찾는 함수
def getParent(parent, x):
    if parent[x] == x: return x
    parent[x] = getParent(parent, parent[x])
    return parent[x]

# 두 부모 노드를 합치는 함수
def unionParent(parent, a, b):
    a = getParent(parent,a)
    b = getParent(parent,b)
    if a < b: parent[b] = a
    else: parent[a] = b

# 같은 부모를 가지는지 확인
def findParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a == b : print("YES")
    else: print("NO")