Disjoint set 에서 중요한 operation 은,
1. union : O(1)
2. find : (n)
이다.

union 은 주어진 두 집합의 모든 원소가 동일한 멤버쉽을 갖게 만드는 연산

find 는 집합의 구성가능 원소가 모두 알려져 있는 상태에서, 특정한 원소가 특정한 집합의 멤버쉽을 갖고 있느냐를 알아내는 연산

(출처 : 엠에센을 통한 1:1 지식 검색 서비스 =33 )
Posted by 스니

티스토리 툴바