P2860 [USACO06JAN] Redundant Paths G
题目描述
贝西和其他牛需要在 $F(1\le F\le 5,000)$ 个牧场间移动（编号为 $1$ 到 $F$）。他们厌倦了走某些特定的路径，因而想要修建一些新路，使得在任意一对牧场之间总有至少两条路线可供选择。目前在每对牧场之间至少有一条路径。当然，他们只能在官方道路上移动。
当前有 $R(F-1\le R\le 10,000)$ 条道路，每条道路连接两个不同的牧场。请你确定必须修建的最小道路数量（每条新道路也要连接两个不同的牧场），使得在任意一对牧场之间至少有两条路线。两条路线只要没有使用同一条道路就被视为合法的（即使经过了相同的牧场）。
在同一对牧场之间可能已有多条路径。修建的新路可以与某条现有道路连接一对相同的牧场。
输入格式
第 $1$ 行：两个用空格分隔的整数：$F$ 和 $R$。
第 $2$ 行到第 $R+1$ 行：每行包含两个用空格分隔的整数，表示某条路径连接的两个牧场。
输出格式
一行一个整数，表示必须修建的新路径数量。
说明/提示
样例解释：
初始路径如下：
可以在 $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$ 的道路），但是添加两条是最少的。
（由 ChatGPT 4o 翻译并人工整改）