【题目来源】
洛谷：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\) 行：一个整数，表示必须修建的新路径数量。
【输入样例】
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
【输出样例】
2
【算法标签】
《洛谷 P2860 Redundant Paths》 #图论# #双连通分量# #USACO# #2006#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 5005; // 最大节点数
const int M = 20005; // 最大边数（无向图需要两倍空间）// 边结构体
struct edge
{int v; // 边的终点int ne; // 下一条边的索引
} e[M];int h[N]; // 邻接表头指针数组
int idx = 1; // 边索引计数器（从2开始，便于异或操作）int dfn[N]; // DFS序（时间戳）
int low[N]; // 通过回边能到达的最小DFN值
int tot; // 时间戳计数器stack<int> stk; // Tarjan算法栈int dcc[N]; // 存储每个节点所属的边双连通分量编号
int cnt; // 边双连通分量计数器int bri[M]; // 标记边是否为桥
int d[N]; // 存储每个边双连通分量的度数int n, m, a, b; // n:节点数, m:边数, a,b:临时变量/*** 添加无向边到邻接表* @param a 边的起点* @param b 边的终点*/
void add(int a, int b)
{e[++idx].v = b; // 记录边的终点e[idx].ne = h[a]; // 新边指向原头节点h[a] = idx; // 更新头节点指向新边
}/*** Tarjan算法求边双连通分量和桥* @param x 当前节点* @param in_edg 进入当前节点的边索引*/
void tarjan(int x, int in_edg)
{// 初始化当前节点的DFN和LOW值dfn[x] = low[x] = ++tot;// 将当前节点压入栈stk.push(x);// 遍历当前节点的所有邻接节点for (int i = h[x]; i; i = e[i].ne){int y = e[i].v; // 邻接节点// 如果邻接节点y未被访问（树边）if (!dfn[y]){tarjan(y, i); // 递归访问ylow[x] = min(low[x], low[y]); // 更新low值// 桥的判断条件：low[y] > dfn[x]if (low[y] > dfn[x]){bri[i] = bri[i ^ 1] = true; // 标记边i和反向边i^1为桥}}// 如果y已被访问且不是来时的边（回边）else if (i != (in_edg ^ 1)){low[x] = min(low[x], dfn[y]); // 通过回边更新low值}}// 如果当前节点是边双连通分量的根if (dfn[x] == low[x]){++cnt; // 增加边双连通分量计数// 弹出栈中节点直到遇到当前节点while (true){int y = stk.top();stk.pop();dcc[y] = cnt; // 记录节点所属的边双连通分量if (y == x){break;}}}
}int main()
{// 输入节点数和边数cin >> n >> m;// 输入所有边并构建无向图while (m--){cin >> a >> b;add(a, b); // 添加边a->badd(b, a); // 添加边b->a（无向图需要双向添加）}// 执行Tarjan算法（假设图连通，从节点1开始）tarjan(1, 0);// 统计每个边双连通分量的度数（桥的数量）for (int i = 2; i <= idx; i++){// 如果当前边是桥if (bri[i]){// 增加目标节点所在分量的度数d[dcc[e[i].v]]++;}}// 统计度数为1的边双连通分量数量（叶子节点）int sum = 0;for (int i = 1; i <= cnt; i++){if (d[i] == 1){sum++;}}// 输出需要添加的最少边数：(叶子节点数+1)/2cout << (sum + 1) / 2 << endl;return 0;
}
【运行结果】
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
2