Union-find Forest

야매 알고리즘? 더보기 알고리즘의 정확한 정의나 의미를 다루지 않고 핵심적인 작동 원리와 코드 예제를 정리하기 위한 시리즈입니다. 전부 짚고 넘어가면 좋겠지만 그럴 지식도 없고, 공부하는 것보다 정리하는데 더 많은 에너지와 시간을 소모할 것 같아서, 기억을 되살리기 위한 아카이브 정도로만 사용할 수 있게 간단하게 정리할 예정입니다. 개요 Disjoint-set: 서로 겹치지 않는 부분 집합들로 이루어진 데이터를 다루기 위한 자료구조. union, find 연산으로 주어진 데이터를 disjoint-set으로 만들어 다룰 수 있다. Disjoint-set은 forest 형태로 표현할 수 있는데, 같은 부분 집합에 있는 원소들이 하나의 tree를 이루는 형태이다. 위 그림의 각 tree가 겹치지 않는 하나의 ..