문제

• 
• 시간 제한: 2초
• 메모리 제한: 512MB

Problem Analysis

두 nodes u, v 사이 경로에 4개 이상의 edge가 존재하는지 확인하는 것이 문제의 목표이다. DFS로 확인하면 된다. 그러나 아래의 경우처럼, 파란색으로 가면 네 번 거치지만, 빨간색으로 가면 세 번 거치는 경우도 존재한다. 따라서, 가능한 모든 경로를 구분하여 조사해야 한다.

Algorithm

DFS를 한다. 일반적인 DFS는 방문한 nodes는 다시 방문하지 않는다. 그러나 이 문제에서는, 이미 방문한 nodes 일지라도 접근한 경로가 다르면 다시 방문하여 조사해야 한다. 따라서, visited 대신 stack에 올라와 있는지를 체크하여, stack에 아직 올라와 있지 않은 nodes를 방문하도록 하여 푼다.

Data Structure

• dfs_stack[]: 각 node가 stack에 올라와 있는지 저장

결과

Other

시간 복잡도가 크기 때문에, 정답을 찾으면 바로 출력해 줄 수 있도록 한다.