서로소 집합(Disjoint Set)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

서로소 집합(a.k.a Union Find)

• 트리의 집합으로 구성된 숲(Forest)이다.
• 각 트리는 ID로 표현되며, 순위(Rank)와 부모에 대한 참조를 갖는다.
• 초기화 시 각 트리는 1 ~ N까지의 ID를 가지며, 순위는 0이고 부모에 대한 참조는 자기 자신이 된다.

 

서로소 집합의 연산들

make_set(x)

• 순위가 0이고 부모에 대한 참조가 자기 자신이며 x를 ID로 갖는 트리를 서로소 집합에 추가한다.

find(x)

• 부모에 대한 참조를 따라 이동하여 트리의 루트를 반환한다.

union(x, y)

1. x, y 각각의 루트를 찾는다.
2. 루트가 같으면 아무 것도 하지 않는다.
3. 루트가 다르면 순위가 높은 루트를 낮은 루트의 부모로 설정한다.

 

서로소 집합의 예

• 크루스칼 알고리즘에서 무방향 그래프의 사이클 발생 여부 검사