题目描述(ID:12206)
标题: 电缆网络
标签: 图结构 割点割边
详情: 电话线路公司(TLC)正在建立一个新的电话电缆网络。它们连接了n个位置。每个地方都有一个交换机。电缆是双向的,连接两个地方,电缆每一端都会连接到当地的交换机中。从每一个地方都可以通过电缆连接到其他地方(可以通过其他交换机到达某地,而未必直接连接)。
有时有的地方停电导致交换机故障。TLC官员认识到,在这样的情况下,除了停电的地方无法到达之外,也可能导致其他地方无法相互连接。在这样的情况下我们会说那个停电的地方是关键的。现在,官员们正在努力编写一个程序来查找所有这些关键地点的数量。帮帮他们。
=========================================================
A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connectingseveral places numbered by integers from 1 to N. No two places have the same number. The linesare bidirectional and always connect together two places and in each place the lines end in a telephoneexchange. There is one telephone exchange in each place. From each place it is possible to reachthrough lines every other place, however it need not be a direct connection, it can go through severalexchanges. From time to time the power supply fails at a place and then the exchange does not operate.The officials from TLC realized that in such a case it can happen that besides the fact that the placewith the failure is unreachable, this can also cause that some other places cannot connect to each other.In such a case we will say the place (where the failure occured) is critical. Now the officials are tryingto write a program for finding the number of all such critical places. Help them.
输入格式:
输入文件由多个部分组成。每个部分描述一个网络。
每个部分的第一行,给出位置个数n(n<100)。
接下来至多有N行,每行首先给出一个位置的编号i,然后出现的编号表示此位置与i相连。请注意,电缆连接是双向的,保证一条电缆一定会在某端点作为i的时候被给出。
每部分以0结束。
文件末尾,在最后一个部分以0结束后,会再给出一个0.
输出格式:
按顺序输出给出网络的关键地点数,每行一个。
样例:

输入

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

输出

1
2

输入

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

输出

0
3
登录并解答