상호 배타적 집합

상호배타적 집합(Disjoint Set)은 유니온 파인드(Union Find) 자료구조로도 불리며

어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합의 합집합은 전체 집합인 자료를 표현합니다.

이 자료구조는 아래의 2가지 함수를 지원합니다.

1. find(u) : 노드 u가 속해있는 집합의 루트를 반환한다.

2. merge(u, v) : 노드 u가 속해있는 집합과 노드 v가 속해있는 집합을 합친다.

find함수로 find(u)와 find(v)의 값이 같다면 u와 v는 같은 집합, 다르다면 다른 집합에 있는 정보를 얻을 수 있으며

다른 집합에 있을 경우 merge함수를 이용하여 두 집합을 합칠 수 있습니다.

추후 그래프파트의 최소 스패닝 트리에서 이 자료구조를 사용하기에 알아두면 좋은 자료구조입니다.

기본 문제

1717번: 집합의 표현

1976번: 여행 가자

4195번: 친구 네트워크