19535번 - ㄷㄷㄷㅈ
인접리스트로 구현한 그래프를 dfs 돌며 답을 구하는데, 7%에서 시간초과가 납니다. 정점이 300,000 간선이 299,999 일때 인접 리스트 dfs는 O(V+E)의 시간복잡도가 아닌가요..? 같은 코드를 bfs deque으로 구현한 코드는 AC를 받았습니다.
24번줄에 G를 2d 리스트로 정의하는 과정에서 시간초과가 날 것 같네요. G= [[] for _ in range(N+1)] 만 해주셔도 통과할듯합니다.
댓글을 작성하려면 로그인해야 합니다.
yoonho0922 2년 전