minbud   3년 전

노드번호를 작은 기준으로 병합했을땐 통과하고 (2번코드)

노드번호를 신경안쓰고 랜덤으로 병합했을땐 시간초과가 발생하는데 (1번코드)

논리적인 이유를 못찾겠습니다. 입력데이터가 특수한가요?

pangitwise   3년 전

노드 번호를 작은 기준으로 병합하면, 항상 큰 집합에 작은 집합을 합하게 되므로 시간을 최적화할 수 있습니다.

zenith82114   3년 전

노드 번호는 말 그대로 번호일 뿐 집합의 크기와는 상관이 없습니다. 집합의 크기가 아닌 번호를 가지고 누구를 누구 밑으로 보낼지 결정하는(+ 그리고 경로 압축을 하지 않는) 구현은 이론적으로 항상 O(n^2)짜리 저격 데이터를 만들 수 있습니다. 예를 들어 아래 예시는 큰 번호를 작은 번호 밑으로 보내는 경우를 저격합니다. 따라서 이 문제는 채점 데이터에 모종의 경향성이 있다고 의심하는 것이 합리적이라고 생각합니다.

N=10
union(9,10)
union(8,9)
union(7,8)
…
union(1,2)

pangitwise   3년 전

개념을 잘못 파악하고 있었네요. 저도 배우고 갑니다.

댓글을 작성하려면 로그인해야 합니다.