[Theory] Graph 3. 서로소 집합(Disjoint-set) aka, Union-Find
서로소 집합(Disjoint-set), 혹은 상호배타 집합이라고도 하는 이놈은 서로 중복 포함된 원소가 없는 집합들을 말한다. 즉, 교집합이 없다. 또한, 이렇게 분리된 집합을 구분하기 위해, 집단에 속한 하나의 특정 구분자를 정하게 되는데 이를 대표자(representative) 라 한다. 이렇게 서로소 집합을 표현하는 방법에는 연결리스트를 이용하는 방법과, 트리를 이용하는 방법이 있다. - 연결리스트 : 같은 집합의 원소들을 하나의 연결리스트로 관리해서, 대표자가 아닌 집합의 원소도 따라 들어가며 찾을 수 있다. - 트리 : 형태가 트리라고 해서, 실제로 링크를 연결해서 구현한 것은 아니고, 대표자를 나타내는 배열 한줄로 각 집합들의 대표자를 관리하고, 대표자가 같은 두 원소는 같은 집합에 있다고 생..
