Problem1151--强连通入门5:无向图双连通1

1151: 强连通入门5:无向图双连通1

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Status] [Submit] [Creator:]

Description

【题意】
        一个无向图有n个点,有m条无向边。
        问增加多少条无向边才能使得原来的图变成双连通。
        什么是双连通:就是少了图中任意一条边,图依旧是强连通图。

【输入格式】
        第一行n个点,m条边无向边。 1 ≤ n ≤ 5000, n-1 ≤ m ≤ 1 0000
        下来m行,每行两个整数,x和y表示一条无向边的两个点。没有重边。

【输出格式】
        一行,至少加多少条无向边,可以使得图是双连通。

【样例1输入】
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
【样例1输出】
2

【样例2输入】
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
【样例2输出】
2

提示:

样例1如下图:

   1   2   3
   +---+---+ 
       |   |
       |   |
 6 +---+---+ 4
      / 5
     /
    /
 7 +
当1 和 6 建一条边, 4 和 7 建一条边,如下:
   1   2   3
   +---+---+ 
   :   |   |
   :   |   |
 6 +---+---+ 4
      / 5  :
     /     :
    /      :
 7 + - - - -
变成双连通或许有多个方案,但是这个方案添加

HINT

注:以边-强连通为标准

Source/Category