이 글에는 지극히 주관적인 내용이 많이 들어있습니다. 분리집합을 구현할 때 보통 가리키는 포인터를 옮기는 방식으로 구현하곤 한다. 하지만 이런 방법은 경로압축도 해야 하고 개인적으로 비직관적이었다. 사실 나는 재귀적인 코드와 작동 과정이 아직 완벽히 이해가 되지 않는다. 그래서 상대적으로 직관적인 smaller to larger(a.k.a 작은거 큰거)를 사용한 분리집합 구현을 소개하고자 한다. (물론 기존 방식보다 느리고 공간도 많이 사용한다.) smaller to larger라는게 애초에 집합을 합치기 위한 연산을 최적화하기 위한 기법이기 때문에 분리집합에도 사용할 수 있다. 기초적인 구조 class DisjointSet { public: vector p; vector ix; int n; } 우선 멤..