【题意】
一个无向图有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 + - - - -
变成双连通或许有多个方案,但是这个方案添加