disjoint set

Disjoint Set DisJoint Set이란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - 즉, 공통 원소가 없는 "상호 배타적"인 부분집합들로 나눠진 원소들에 대한 자료구조 - Disjoint Set=서로소 집합 자료구조 Union-Find Union-Find란? Disjoint Set을 표현할 때 사용하는 알고리즘 -집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현 -아래의 세가지 연산을 이용하여 Disjoint Set을 표현 Union-Find의 연산 - make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. - union(x,y) x가 속한 집합과 y가..