yoonho0922   2년 전

인접리스트로 구현한 그래프를 dfs 돌며 답을 구하는데, 7%에서 시간초과가 납니다.
정점이 300,000
간선이 299,999
일때 인접 리스트 dfs는 O(V+E)의 시간복잡도가 아닌가요..?

같은 코드를 bfs deque으로 구현한 코드는 AC를 받았습니다.

itsantiago   2년 전

24번줄에 G를 2d 리스트로 정의하는 과정에서 시간초과가 날 것 같네요. G= [[] for _ in range(N+1)] 만 해주셔도 통과할듯합니다.

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