MST
-
Disjoint Sets자료구조 2019. 9. 2. 18:55
n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조 n개의 원소가 n개의 set으로 초기화됨 (MakeSet()) Tree를 사용하는 것이 효율적. Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j) Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n)) void simpleUnion(int i, int j) {parent[i] = j;} 효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침 두 set의 height가 같으면 union된 set의 height 증가 Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포..