Union-Find를 rollback하려 합니다. 경로 압축이 변경 이력과 충돌하는 이유와 대안은 무엇인가요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

rollback은 union 때 바꾼 parent·rank·size를 스택에 기록해 되돌리는 방식이 가능합니다. 경로 압축은 find 중 많은 parent를 바꾸므로 그 변경까지 기록해야 해 단순 rollback과 비용이 충돌합니다.

union by size만 쓰거나 검증된 rollback variant를 선택합니다. 같은 집합 union의 무변경 기록·snapshot 위치·metadata 복원을 시험합니다. 온라인 임의 간선 삭제를 기본 DSU가 해결한다고 하지 않습니다.

이해가 드러나는 지점을 확인해 보세요.

rollback은 union 때 바꾼 parent·rank·size를 스택에 기록해 되돌리는 방식이 가능합니다. 경로 압축은 find 중 많은 parent를 바꾸므로 그 변경까지 기록해야 해 단순 rollback과 비용이 충돌합니다.
온라인 임의 간선 삭제를 기본 DSU가 해결한다고 하지 않습니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: rollback은 union 때 바꾼 parent·rank·size를 스택에 기록해 되돌리는 방식이 가능합니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.