hellogaon

상호배타적 집합(Disjoint Set)은 유니온 파인드(Union Find) 자료구조로도 불리며어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합의 합집합은 전체 집합인 자료를 표현합니다.이 자료구조는 아래의 2가지 함수를 지원합니다. 1. find(u) : 노드 u가 속해있는 집합의 루트를 반환한다.2. merge(u, v) : 노드 u가 속해있는 집합과 노드 v가 속해있는 집합을 합친다. find함수로 find(u)와 find(v)의 값이 같다면 u와 v는 같은 집합, 다르다면 다른 집합에 있는 정보를 얻을 수 있으며다른 집합에 있을 경우 merge함수를 이용하여 두 집합을 합칠 수 있습니다.추후 그래프파트의 최소 스패닝 트리에서 이 자료구조를 사용하기에 알아두면 좋은 자료구조입니다. 기본 문제..