多路径

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23: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 + - - - -