분리 집합 (Disjoint Set) : Union-Find 알고리즘

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

위 문제를 풀다가 몰라서 정리하고 간다.

 

Union-Find 알고리즘은 분리 집합(Disjoint-set) 자료구조를 구현하는 데 사용된다.

 

Union: 두 개의 집합을 하나로 합치는 연산. 두 집합을 합치기 위해 루트를 찾아서 하나의 집합으로 만듦.

Find: 주어진 원소가 주어진 집합의 루트를 찾는 연산. 이 연산을 통해 두 원소가 같은 집합에 속해 있는지 확인 가능 (두 집합의 루트를 비교하여 확인)

 

#두 개의 집합이 같은 집합인지 확인, 아닐경우 하나로 합침
def union(x, y):
    x = find(x)
    y = find(y) #주어진 x, y의 루트를 찾아서
    if x == y: #루트가 같다면 동일한 집합
        return
    parent[x] = y #아니라면 같은 집합으로 합쳐주기
    #x의 부모는 y
    return

#주어진 집합의 루트를 찾음
def find(x):
    if parent[x] == x: #주어진 값이 루트면 리턴
        return x
    parent[x] = find(parent[x]) #아니면 부모를 찾아 재귀
    return parent[x]