[Algorithm] Union-Find Algorithm

Union-Find Algorithm - Disjoint Set을 표현할 때 사용하는 알고리즘 Disjoint Set - 각 집합들에 대해 서로 공통 원소가 없는 집합 :: 서로소 집합 자료구조 트리 구조를 사용하면 가장 효율적으로 구현할 수 있다 최소 힙과 비슷하게 root를 가장 작은 값으로 설정해주면 편리하다 Union-Find 연산 (1) init-set(x) - 각 node들을 본인의 번호로 초기화 번호 1 2 3 4 5 6 root 1 2 3 4 5 6 (2) union(x, y) - x가 속한 집합과 y가 속한 집합을 합친다 ex) (1, 3) (2, 4, 5, 6) 합치기 - 합치고, 각자 번호를 해당 tree의 root번호로 변경해준다 바로 위의 부모 node로 변경하는게 아니라 최종적인..

2022.02.09