Disjoint Set

서로소인 집합들에 대한 정보를 저장하고 조작하는 자료구조다. Union Find data structure 라고 부르기도 한다. 어떤 한 원소가 속한 집합을 찾는 연산, 어떤 두 집합을 합치는 연산 두가지를 빠른 시간에 수행할 수 있다.

• 공간 복잡도 : O(n)
• 시간 복잡도
  • 초기화 : O(n)
  • 집합 찾기 : O(alpha(n))
  • 합집합 : O(alpha(n))

집합의 원소 추적

어떤 집합에 속한 원소들의 목록을 유지하고 싶은 경우가 있다. 이럴 때는 아래와 같이 코드를 변경하면 된다. 원소들의 목록을 합치는 시간은 전부 다 합해서 O(n*logn) 이다. 항상 작은쪽을 큰쪽에 합치기 때문이다. linked list 를 잘 사용하면 더 빠르게 수행할 수 있을 것 같다.