[알고리즘] Disjoint Set (서로소 집합) - Union, Find

Disjoint Set (서로소 집합)

두 개 이상의 집합을 형성할 때, 교집합이 공집합이 되도록 구성하는 자료구조

ex) A={1, 2, 3}과 B={4, 5, 6}은 서로소 집합

ex) C={1, 3, 5}과 D={3, 5, 7}은 서로소 집합이 아니다.

 

Disjoint Set은 대개 Tree로 구성한다.

항상 Parent-Child관계와 Root Node가 존재한다.

Disjoint Set 연산

Disjoint Set은 두 가지 연산을 지원한다.

Union(x, y)

x가 속하고 있는 집합과 y가 속하고 있는 집합을 합친다.

이때 x와 y가 같은 집합 내에 있다면 합치지 않는다.

Find(x)

x가 속하고 있는 집합을 구한다.

Python 코드

parent = [p for p in range(v+1)] # 부모를 자기 자신으로 초기화
    
def find_parent(parent, x):
    if parent[x] !=x:
    	parent[x] = find_parent(parent, parent[x]) # 경로 압축
        return parent[x]
    return x

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
       	parent[a] = b

 

참고: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html,
https://0x15.tistory.com/34,
https://velog.io/@woo0_hooo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-union-find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98,
https://freedeveloper.tistory.com/387,