Message
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 200
Solved: 57
- Description
- HUST ACM/ICPC Team has some AIs. AIs are connected to a network. They use the network sharing ideas, so that they would get smarter. When an AI comes up with an idea, he would transmit it to all his neighbor AIs. But one day an AI found that his idea can't be got by every AI in the network for the cable is directed. He decided to add some cable to make every AI's idea can reach all other AIs. But all cable he can use is directed and very expensive, so he has to find the minimum number of cable to add. Now you are to teach the AI how to work it out.
- Input
- The input contains multiple test cases. The first line of each case contains an integer N: the number of AIs in the network(2 <= N <= 100). The AIs are identified by the first N positive integers. Each of the next N lines describes a list of neighbors. The line i+1 contains the identifiers of the neighbors of AI i. Each list ends with a 0. If one doesn't have any neighbor, it contains a 0 alone in the line. The file is ended with a line containing -1.
- Output
- Your program should write only one line containing the minimum number of cable to add.
- sample input
-
5 2 4 3 0 4 5 0 0 0 1 0 -1
- sample output
-
2
- hint
- source
- <a href="http://aifreedom.com/">Ai.Freedom</a>