그림 1 은 자동차 경주 코스의 예이다. 0 은 시작점이고 N 은 도착 점이다.
(예에서는 N=9) 화살 표는 일방통행 표시이다.
참자자는 길을 통해서 한 곳에서 다른 한 곳으로 이동한다.
코스는 아래와 같은 특징을 가진다.
참가자는 도착지로 가기위해서 코스의 모든 포인트를 다 방문할 필요는 없다. 그러나 어떤 점은 반드시 거쳐야 한다.
예에서는 0,3,6,9 코스가 주어질 때 , 반드시 거쳐야하는 코스의 포인트를 결정하는 프로그램을 작성하시오.(단 출발점, 도착점 제외)
경기가 이틀 연속 개최된다고 가정하자. 이를 목적으로 코스가 두개의 코스로 분리되어야 하고자 할 때 splitting 포인터를 찾는 프로그램도 구하고자 한다.
출발지와 도착지를 제외하고 두 개의 코스로 분리하되 두 개의 코스 사이에는 공통의 길이없고 또한 나뉘어진 길도 위에서 정의한 코스의 성질을 만족하는 해야 하는 점이다.예에서는 3 점이 splitting point 이다.
입력은 최대 50 까지의 점과 100 개의 화살표를 가진다. N+2 줄이 주어지고 N+1 줄은 0 번 점부터 N 점에서 나가서 만나는 점 번호가 입력된다.
각 점의 끝은 -2 로 인식하고 마지막 줄은 -1 로 입력의 끝으로 인식한다.
출력은 두 줄로 구성되고 첫 줄은 반드시 거쳐야 하는 점 , 다른 한 줄은 splitting point 를 오름차순으로 출력한다.
입력 1 2 -2 3 -2 3 -2 5 4 -2 6 4 -2 6 -2 7 8 -2 9 -2 5 9 -2 -2 -1 출력 2 3 6 1 3 출처: IOI'95
입력 출력
출처: 채점 데이터: