# 시간 복잡도


+ 경로 압축 및 Rank (or Size): O(log* n) ~ O(1)

+ 경로 압축만: Find 쿼리당 amortized O(log n)


경로를 압축하지 않고 반으로만 줄이는 기법도 있는데 (Path halving), 시간 복잡도가 같으면서도 2-pass 루프나 재귀를 이용할 필요가 없음

이는 while (p[x] != x) { x = p[x] = p[p[x]]; } 같은 방법으로 사용할 수 있음.


# 예제


## 기초

집합의 표현: https://www.acmicpc.net/problem/1717

Liars and Truth Tellers: https://www.acmicpc.net/problem/5859

문명: https://www.acmicpc.net/problem/14868


## Next 이용

Gates: https://www.acmicpc.net/problem/10775

포스터: https://www.acmicpc.net/problem/13167