Union-Find — 두 최적화가 O(N) 을 상수로 만든다Union-Find 는 그룹마다 root 대표를 두고 같은 그룹인지 판정한다. 최적화 없는 구현은 사슬 트리에서 find 가 O(N) 까지 늘어지지만, path compression 과 union by rank 를 더하면 사실상 상수가 된다.알고리즘Union-Find그래프자료구조Python