nuclear852   4년 전

계속 84%에서 시간초과가 납니다....

어느 테스트케이스가 문제가 되는지 잘 모르겠어요...


일단 제 코드는 방문하지 않은 정점에 대해서 쭉 탐색하면서

정점들을 vector에 넣어주고요,

해당 사이클에서 방문된 정점과 만나면 그 방문된 정점에서부터 vector 끝까지에 담겨있는 정점들에게

얘네들은 사이클을 만들 수 있다고 표시해줘요.

그 다음 사이클을 못 만드는 애들의 갯수로 다 더해주면 된다고 생각을 했는데... 계속 84%인가 82%인가에서 시간 초과가 뜨네여ㅠㅠㅠ 


코드를 어떻게 수정하는 방향으로 바꾸는 게 좋을까요?


--코드삭제--

etaehyun4   4년 전

만약

4 -> 1 -> 2 -> 3 -> 1

이런게 있으면 1번에서 1->2->3->1 을 찾아내고 4에서 1->2->3->1 을 또 찾겠죠?


그럼 극단적인 케이스로 1부터 50000까지가 사이클이고 나머지는 다 1번으로만 향한다고 했을 때, 시간복잡도는 거의 O(N^2) 가 될 것입니다. 그래서 시간초과가 날 것 같네요


한번 인지한 사이클은 더이상 보지 않도록 수정해보세요

nuclear852   4년 전

정말 감사합니다!!

해결했어요~

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