자료구조
[자료구조 / C++] Disjoint Set
Disjoint Set 특징 그룹이 있다. 각 그룹은 공통된 요소들이 없다. (상호 배타적) 원소가 어떤 그룹에 속해있는가? (Find) 2개의 그룹을 어떻게 합칠 것인가? (Union) 특징에 대한 구체화 그룹이 있다 = 그룹을 특정할 수 있는 "그룹명"은 무엇으로 할까? = 그룹의 창시자 OR 임의 지정으로 (특정 원소 = 그룹의 상징 = Root)을 만든다. 각 그룹은 공통된 요소들이 없다. (상호 배타적) = 복잡도가 낮다. = 오직 하나의 Root를 가지고 있다. 원소가 어떤 그룹에 속해있는가? (Find) = Root를 찾으면 된다. How? = 최상위 부모까지 올라간다. = 따로 Root를 저장할 수도 있다. 2개의 그룹을 어떻게 합칠 것인가? (Union) = 그룹의 Root를 찾는다. =..
