Union & Find

• 트리의 연결성을 표현할수 있는 구조입니다.
• 트리의 부모를 찾는 find() 메소드와 두개의 트리를 합쳐주는 union 메소드로 나누어 집니다.
• 초기 트리의 각각의 노드들은 자기 자신을 루트로 가지고 있습니다.
• 트리를 연결할때마다 루트를 갱신해서 트리를 연결합니다.

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    x = find(x)
    y = find(y)

    if x<y:
        parent[y] = x
    else:
        parent[x] = y

이미지 출처

• https://m.blog.naver.com/ndb796/221230967614