1199번 - 오일러 회로
재채점을 거듭하면서 까다로운 TC가 추가됨에 따라,
블로그 등지에 흔히 소개되는 naive한 O(VE) Hierholzer's algorithm은 더이상 시간 내에 통과를 못 합니다.
쉽게 말하자면, 그래프 구조를 인접행렬로 저장해서 정점을 찾는데 O(V)가 걸리거나,
인접리스트로 저장해서 간선을 삭제하는데 O(V)가 걸리는 경우 시간 초과가 발생합니다.
어느 자료구조를 택하든 이 O(V)의 탐색시간을 O(logV) 또는 O(1)로 최적화해야 AC를 받을 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
blast 4년 전 18
재채점을 거듭하면서 까다로운 TC가 추가됨에 따라,
블로그 등지에 흔히 소개되는 naive한 O(VE) Hierholzer's algorithm은 더이상 시간 내에 통과를 못 합니다.
쉽게 말하자면, 그래프 구조를 인접행렬로 저장해서 정점을 찾는데 O(V)가 걸리거나,
인접리스트로 저장해서 간선을 삭제하는데 O(V)가 걸리는 경우 시간 초과가 발생합니다.
어느 자료구조를 택하든 이 O(V)의 탐색시간을 O(logV) 또는 O(1)로 최적화해야 AC를 받을 수 있습니다.