- 서로소 집합 = 상호베타집합 = 서로 중복되는 원소가 없는 집합 = 교집합 X
- 집합에 속한 하나의 특정 멤버를 “대표자” 라고 한다
서로소 집합을 구성하고 이용할 때 사용하는 3가지
Make-Set(a) : 개별적인 집합을 만들기. 대표자가 자기 자신인 상태.
Union(x,a) : a집합의 대표자를 x집합으로 설정하기 : 집합과 집합을 연결하는것임에 유의. 개별원소 아님!
Find-Set(a) : 해당 집합의 대표자 집합을 찾기
예시
Make-Set(x) , Make-Set(y) , Make-Set(a) , Make-Set(b)
Union(x, y) y의 대표 집합을 x로 설정
Union(a, b)
Find-Set(y) retum x (representative)
Find-Set(a) retum a (representative)
Union(x, a) 이제 Find-Set(x) , Find-Set(y), Find-Set(a) , Find-Set(b) 모두 retum x (representative)
서로소 집합 구현 자료구조 2가지
- 연결리스트
- head로 연결시키는 구조
- tail도 관리해야 하는 이유 : 묶음을 한번에 붙이는 작업을 위함
-
트리
유형
- 그룹의 개수 구하기 유형
- 그룹의 정보가 주어지고 , 두 개의 주어진 정보가 같은 그룹인지 확인하는 유형
- 양방향 그래프에서 사이클 판별
관련문제
- 다리만들기1,2 (백준)