多路径

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 rpathsa.in 输出文件 rpathsa.out

有F (1 <= F <= 5,000)个牧场(标号为:1..F)。奶牛们厌倦了老是走重复的路径。它们想在牧场之间建立一些新的边,使得任意两个牧场至少有两条不同的路径。现在不同的牧场之间已经至少有一条路径了。

给出R (F-1 <= R <= 10,000)条边,每条边连接两个不同的牧场。计算最少需要建立多少条边,使得任意两个牧场之间至少有两条不同的路径。只要没有访问相同的边,那么就可以认为是不同的路径,就算是访问的中间牧场有相同.

注意:两个不同的牧场之间可能有多条不同的边,你依然可以在这两个牧场间建立一条不同的新边。

输入格式:

*第1行:两个不同的整数: F、R

*第2..R+1行:每行两个不同的牧场,表示它们之间有一条边。

输入解释:

   1   2   3
   +---+---+ 
       |   |
       |   |
 6 +---+---+ 4
      / 5
     /
    /
 7 +


样例输入:rpathsa.in
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7


输出格式:

*一行:  一个整数,算最少需要建立多少条新边,使得任意两个牧场之间至少有两条不同的路径。

样例输出:rpathsa.out

2

输出解释:

在牧场1和6之间建立一条新边,在牧场4和7之间建立一条新边.


以下是部分路径(左边是牧场,右边是不同的路径):

1 - 2: 1 -> 2 and 1 -> 6 -> 5 -> 2

1 - 4: 1 -> 2 -> 3 -> 4 and 1 -> 6 -> 5 -> 4

3 - 7: 3 -> 4 -> 7 and 3 -> 2 -> 5 -> 7

你可以发现,任意两个不同牧场之间都至少有两条不同的路径。

   1   2   3
   +---+---+ 
   :   |   |
   :   |   |
 6 +---+---+ 4
      / 5  :
     /     :
    /      :
 7 + - - - -