Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Street Race
发信站: 哈工大紫丁香 (2002年03月29日13:52:00 星期五), 站内信件

Task: Street Race
Figure 1 gives an example of a course for a street race. You see some points
, labeled from 0 to N (here N=9), and some arrows connecting them. Point 0 i
s the start of the race; point N is the finish. The arrows represent one-way
 streets. The participants of the race move from point to point via the stre
ets, in the direction of the arrows only. At each point, a participant may c
hoose any outgoing arrow.
Figure 1: A street course with 10 points
A well-formed course has the following properties:
Every point in the course can be reached from the start.
The finish can be reached from each point in the course.
The finish has no outgoing arrows.
A participant does not have to visit every point of the course to reach the 
finish. Some points, however, are unavoidable. In the example, these are poi
nts 0, 3, 6, and 9. Given a well-formed course, your program has to determin
e the set of unavoidable points that all participants have to visit, excludi
ng start and finish (Subtask A).
Suppose the race has to be held on two consecutive days. For that purpose th
e course has to be split into two courses, one for each day. On the first da
y, the start is at point 0, and the finish at some `splitting point'. On the
 second day, the start is at this splitting point and the finish is at point
 N. Given a well-formed course, your program has to determine the set of spl
itting points (Subtask B). A point S is a splitting point for the well-forme
d course C if S differs from the start and the finish of C, and the course c
an be split into two well-formed courses that have no common arrows and that
 have S as only common point. In the example, only point 3 is a splitting po
int.
Input Data
The file INPUT.TXT describes a well-formed course with at most 50 points and
 at most 100 arrows. There are N+1 lines in the file. The first N lines cont
ain the endpoints of the arrows that leave from the points 0 through N-1 res
pectively. Each of these lines ends with the number -2. The last line contai
ns the number -1.
Output Data
Your program should write two lines to the file OUTPUT.TXT. The first line s
hould contain the number of unavoidable points in the input course, followed
 by the labels of these points, in any order (Subtask A). The second line sh
ould contain the number of splitting points of the input course, followed by
 the labels of all these points, in any order (Subtask B).
Example Input and Output
Figure 2 gives possible input and output files for the example of Figure 1.
_____________     ______________
| INPUT.TXT |     | OUTPUT.TXT |
|___________|     |____________|
| 1 2 -2    |     | 2 3 6      |
| 3 -2      |     | 1 3        |
| 3 -2      |     |____________|
| 5 4 -2    |
| 6 4 -2    |
| 6 -2      |
| 7 8 -2    |
| 9 -2      |
| 5 9 -2    |
| -1        |
|___________|
Figure 2: Example input and output


--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]