网络通讯
   

　　农夫John的奶牛喜欢通过E-mail互相联系，所以它们建立了一个网络来互相通讯。这些机器可沿路线发送E-mail。如果存在一个由计算机组成的序列a1，a2，..., an，其中a1与a2相连，a2与a3相连…，则a1和an可以互相传送E-mail。

　　不幸的是，如果一个奶牛偶然间踩到计算机上或者农夫John开车经过，则机器将停止工作。这意味着，这个计算机将不能接发E-mail，则与这个计算机的连接将不能再使用。

　　两个通讯的奶牛正在考虑至少发生多少这种事故，才能使它们不能用他们的计算机进行互相通讯。写出一个程序，为他们计算这个最小值并找出对应这个最小值的那一组机器。

　　例如，网络：
　　　　　　1*
　　　　　　／
　　　　3* --2*

　　表示3个计算机用两条线连接，我们想在1，2之间传递信息。直线连接了1，3和2，3。如果计算机3被破坏，则从1到2无法进行通讯。

　　输入：

　　网络的第一行包含4个整数：n，m，a，b。第一个数字n是网络上计算机的数目，第二个数字m是每对计算机之间直接连接的数目，最后两个数字a和b是通讯的两个奶牛所使用的计算机的ID号码。

　　计算机的数目将不大于40，每个连接是唯一而且双向的(如果c1与c2连接，则c2也与c1连接)。每两个计算机之间至多连一根线。对于这个任务，终端a和b不会直接相连。

　　输入文件名为INPUT.C3，输入文件可能包含几个网络，文件的结束行为0 0 0 0。

　　输出∶

　　对于每个网络，将有三行输出。第一行的形式为"Network # n"，其中n是数据的编号；第二行是使终端a和b不再连接的最少损坏计算机数；第三行是使a和b不再连接而损坏的计算机列表，之间用空格隔开。注意，a和b不能被损坏。

　　输出文件名为OUTPUT.C3

　　sample input

　　3 2 1 2
　　1 3
　　2 3
　　8 14 1 2
　　1 3
　　1 6
　　1 7
　　1 8
　　2 3
　　2 4
　　2 5
　　2 6
　　2 7
　　3 6
　　4 5
　　4 7
　　4 8
　　7 8
　　0 0 0 0

　　sample output

　　Network # 1
　　1
　　3
　　Network # 2
　　4
　　3 4 6 7
　　(3 6 7 8也对)。
　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有