연결 요소의 정보를 저장함

1. find → x가 속한 트리의 루트를 구하는 함수
2. union(a, b) → 두 트리를 합치는 함수(a의 루트 b의 루트를 구한 뒤, 하나가 다른 하나의 아래로 가도록)

find(a) == find(b) → a, b가 같은 집합이다.

find 함수

1. basic 구현 O(N)

1. 최적화 구현
   1. 경로 압축 (중간 경로를 다 끊어서 루트에 붙여버림)
      1. amortized O(lonN) → 한번은 O(N)일 수 있지만, N번하면 log(N)

union 함수

1. basic 구현 O(N) → find의 시간 복잡도와 같음

   

2. 최적화 구현 union by rank (이것도 find 최적화임)

boj 18116

size