Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Problem 3: Network of Schools
发信站: 哈工大紫丁香 (2002年03月29日13:54:52 星期五), 站内信件

Problem 3: Network of Schools
A number of schools are connected to a computer network. Agreements have bee
n developed among those schools: each school maintains a list of schools to 
which it distributes software (the "receiving schools"). Note that if B is i
n the distribution list of school A, then A does not necessarily appear in t
he list of school B
You are to write a program that computes the minimal number of schools that 
must receive a copy of the new software in order for the software to reach a
ll schools in the network according to the agreement (Subtask A). As a furth
er task, we want to ensure that by sending the copy of new software to an ar
bitrary school, this software will reach all schools in the network. To achi
eve this goal we may have to extend the lists of receivers by new members. C
ompute the minimal number of extensions that have to be made so that whateve
r school we send the new software to, it will reach all other schools (Subta
sk B). One extension means introducing one new member into the list of recei
vers of one school.
　
Input Data
The first line of file INPUT.TXT contains an integer N: the number of school
s in the network (2<=N<=100). The schools are identified by the first N posi
tive integers. Each of the next N lines describes a list of receivers. The l
ine i+1 contains the identifiers of the receivers of school i. Each list end
s with a 0. An empty list contains a 0 alone in the line.
　
Output Data
Your program should write two lines to the file OUTPUT.TXT. The first line s
hould contain one positive integer: the solution of subtask A. The second li
ne should contain the solution of subtask B.
　
Example Input and Output
Figure 1 gives a possible input file and the corresponding output file.
　
----------------------------------------------------------------------------
----
INPUT.TXT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT.TXT
1
2

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

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