2021.06.26
[C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합
디스조인트-셋(Disjoint-Set) 디스조인트-셋(Disjoint-Set) 또는 유니언-파인드(Union-Find) 자료구조 다음과 같이 불림. 서로소 집합 자료구조 상호 배타적 집합 자료구조 트리 형태로 구성된 포레스트(Forest) 각각의 원소는 숫자 ID 에 의해 표현됨. 랭크(Rank) 와 부모에 의한 포인터를 가짐. 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성됨. 각각의 원소는 하나의 트리를 나타냄. 공통의 원소를 갖지 않는 원소 집합을 표현하기 위해 사용됨. 지원 연산 make-set(x) x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가함. 새로 추가한 원소의 랭크 : 0 원소의 부모 포인터는 자기 자신을 가리키도록 설정함. 그림 설명 원 안에 적힌 숫자 : 원소 ID 괄호 ..
