Sean :: Dev

Disjoint-set Algorithm (서로소 집합 알고리즘) 집합, 그룹을 관리하는 알고리즘 각 그룹을 트리구조로 관리 크게 2가지의 연산으로 구성된다. find(x) : x번 노드의 root를 찾는 함수 link(x, y) : x 노드가 속한 그룹과 y 노드가 속한 그룹을 합치는(연결하는) 함수 또한 위 연산을 위해, parent[i] : i번 노드의 부모로 정의되는 배열이 사용된다. 아래의 내용은 codeground 사이트에서 가져온 내용 Disjoint-Set 서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는 함수 ..