ldh5730   4년 전

안녕하세요 다시 문제를 풀어 보던 중 문제가 잘못 된게 아닌가 싶어서 이렇게 질문 남깁니다.

제가 이 문제를 풀었을 때, SCC를 구성 한 다음 SCC를 각각 노드로 보면서 진입차수가 0인 SCC가 1개이면 그 안의 노드들을 오름 차순으로 정렬하는 방식으로 문제를 해결 했습니다.

그런데 제가 문제를 다시 접근 했을 때 생각하게 된 부분은 진입 차수가 0인 SCC가 1개 더라도, 이 SCC와 연결된 또 다른 SCC가 2개 이상일 경우 모든 노드를 방문 하기 어렵다는 것 입니다.

제가 생각 하는 반례 첨부 합니다.


1
6 6
0 1
1 2
2 0
0 5
1 3
2 4

위의 경우 (0,1,2)가 진입 차수가 0인 SCC에 해당하고, 각각 (3),(4),(5)가 SCC에 해당합니다. 이런 경우

정답은 Confused가 되어야 하는 거 아닌가요? 확인 한번 해주시면 감사하겠습니다.

portableangel   4년 전

대개 "모든 노드를 방문할 수 있는 노드 u"는, 다른 모든 노드 v에 대하여 u->v의 경로가 존재하는 노드를 의미합니다. 질문자님은 u에서 출발한 한 명의 선수가 다른 모든 정점을 방문해야 한다고 생각하신 점에서 혼란이 있는 듯한데, 이 문제에서 말하는 시작점은 다른 모든 노드로 가는 경로가 각각 존재하기만 하면 됩니다.

ldh5730   4년 전

그런거였군요. 명쾌하게 이해 됐습니다 감사합니다~!

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