0x60图论（练习）13：分离的路径

P2860 [USACO06JAN] Redundant Paths G

题目描述

一个无向连通图有 $n$ 个点，有 $m$ 条无向边。 问增加多少条无向边才能使得原来的图变成"边双连通"。 边双连通：没有割边的无向连通图。

贝西和其他牛需要在 $F(1\le F\le 5,000)$ 个牧场间移动（编号为 $1$ 到 $F$）。他们厌倦了走某些特定的路径，因而想要修建一些新路，使得在任意一对牧场之间总有至少两条路线可供选择。目前在每对牧场之间至少有一条路径。当然，他们只能在官方道路上移动。

当前有 $R(F-1\le R\le 10,000)$ 条道路，每条道路连接两个不同的牧场。请你确定必须修建的最小道路数量（每条新道路也要连接两个不同的牧场），使得在任意一对牧场之间至少有两条路线。两条路线只要没有使用同一条道路就被视为合法的（即使经过了相同的牧场）。

在同一对牧场之间可能已有多条路径。修建的新路可以与某条现有道路连接一对相同的牧场。

输入格式

第 $1$ 行：两个用空格分隔的整数：$F$ 和 $R$。

第 $2$ 行到第 $R+1$ 行：每行包含两个用空格分隔的整数，表示某条路径连接的两个牧场。

输出格式

一行一个整数，表示必须修建的新路径数量。

输入输出样例 #1

输入 #1

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

输出 #1

2

说明/提示

样例解释：

初始路径如下：

可以在 $1$ 和 $6$ ， $4$ 和 $7$ 间修建新路。

一些例子：

• $1 - 2$：$1 \to2$ 或 $1 \to6 \to5 \to2$
• $1 - 4$：$1 \to2 \to3 \to4$ 或 $1 \to6 \to5 \to4$
• $3 - 7$：$3 \to4 \to7$ 或 $3 \to2 \to5 \to7$

可以发现，每对牧场之间都有至少两条路径。

其他道路修建方式也可能解决问题（例如从 $6$ 到 $7$ 的道路），但是添加两条是最少的。

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

（由 ChatGPT 4o 翻译并人工整改）