alohajihwan   8달 전

dfs의 시간복잡도는 O(V+E) 인걸로 알고 있습니다. 지금 이 문제에서는 V = 100000 E = 100000개 이므로 시간복잡도는 V로 10만 인데 왜 시간초과 가 나오는지 모르겠습니다. 각 노드당 간선이 하나이므로 tree edge , back edge 를 제외한 간선이면 return 시켜줘서 최소한 덜 연산하도록 코드를 작성하였습니다.

koosaga   8달 전

test case가 좀 빡빡하게 들어와서 dfs로는 풀 수 없게 만들어진거 같습니다. (600ms가 빠른 편이니..)

alohajihwan   8달 전

답변 감사합니다.

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