问题1226--修桥

1226: 修桥

时间限制: 1 Sec  内存限制: 128 MB
提交: 94  解决: 42
[提交] [状态] [讨论版] [命题人:]

题目描述

某群岛有N个小岛,有M座桥连通这些小岛,使得每两个小岛之间都可以相互访问到。因为游客越来越多,有些桥需要重新修缮,因为建设者希望再添加一些桥,使得当某座桥正在被修时,游客可以通过其他桥访问任何小岛。

换而言之,就是希望添加桥之后,整个图没有割边,任意两座小岛都有两条截然不同的路径

输入

首先输入NM

然后接下来M行,每行输入两个数字A,B,表示岛A和岛B有桥连通。

岛的编号为1~N, 输入的数据保证一开始整个岛是连通

输入可能有重边,比如

1 2

1 2

表示岛1和岛2有两座桥

输出

输出至少要添加多少桥

样例输入 Copy

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

样例输出 Copy

2

提示

【样例说明】

原始图:

 

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

可以添加1647的桥,使得任意两个点之间双连通

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

 

【数据规模和约定】

1<=N<=5000,   N-1<=M<=10000

来源/分类