【题目来源】
洛谷：P1656 炸铁路 - 洛谷
【题目描述】
A 国派出将军 uim，对 B 国进行战略性措施，以解救涂炭的生灵。
B 国有 \(n\) 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。
uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。
uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。
然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？
【输入】
第一行 \(n,m\ (1 \leq n\leq 150\)，\(1 \leq m \leq 5000)\)，分别表示有 \(n\) 个城市，总共 \(m\) 条铁路。
以下 \(m\) 行，每行两个整数 \(a, b\)，表示城市 \(a\) 和城市 \(b\) 之间有铁路直接连接。
【输出】
输出有若干行。
每行包含两个数字 \(a,b\)，其中 \(a<b\)，表示 \(\lang a,b\rang\) 是 key road。
请注意：输出时，所有的数对 \(\lang a,b\rang\) 必须按照 \(a\) 从小到大排序输出；如果 \(a\) 相同，则根据 \(b\) 从小到大排序。
【输入样例】
6 6
1 2
2 3
2 4
3 5
4 5
5 6
【输出样例】
1 2
5 6
【算法标签】
《洛谷 P1656 炸铁路》 #模拟# #搜索# #图论# #并查集# #最短路# #Tarjan# #洛谷原创#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 155; // 最大节点数
const int M = 10005; // 最大边数// 边结构体
struct edge
{int u, v; // u:起点, v:终点
};// 桥结构体，支持排序
struct bridge
{int x, y; // 桥的两个端点// 重载小于运算符，用于排序bool operator<(const bridge &t) const {if (x == t.x) return y < t.y;return x < t.x;}
} bri[M]; // 存储所有桥int n, m, a, b, cnt; // n:节点数, m:边数, cnt:桥的数量
int dfn[N]; // DFS序（时间戳）
int low[N]; // 通过回边能到达的最小DFN值
int tot; // 时间戳计数器vector<edge> e; // 存储所有边的数组
vector<int> h[N]; // 邻接表，h[i]存储从节点i出发的边在e中的索引/*** 添加无向边到图中* @param a 边的起点* @param b 边的终点*/
void add(int a, int b)
{e.push_back({a, b}); // 添加边到边数组h[a].push_back(e.size() - 1); // 记录边在数组中的索引
}/*** Tarjan算法寻找桥* @param x 当前节点* @param in_edg 进入当前节点的边索引（用于避免重复访问）*/
void tarjan(int x, int in_edg)
{// 初始化当前节点的DFN和LOW值dfn[x] = low[x] = ++tot;// 遍历当前节点的所有出边for (int i = 0; i < h[x].size(); i++){int j = h[x][i]; // 当前边在e数组中的索引int y = e[j].v; // 邻接节点// 如果邻接节点y未被访问（树边）if (!dfn[y]){tarjan(y, j); // 递归访问ylow[x] = min(low[x], low[y]); // 更新low值// 桥的判断条件：low[y] > dfn[x]if (low[y] > dfn[x]){// 记录桥（确保x<y，便于排序输出）if (x < y)bri[++cnt] = {x, y};elsebri[++cnt] = {y, x};}}// 如果y已被访问且不是来时的边（回边）else if (j != (in_edg ^ 1)){low[x] = min(low[x], dfn[y]); // 通过回边更新low值}}
}int main()
{// 输入节点数和边数cin >> n >> m;// 输入所有边并构建无向图while (m--){cin >> a >> b;add(a, b); // 添加边a->badd(b, a); // 添加边b->a（无向图需要双向添加）}// 对每个未访问的节点执行Tarjan算法for (int i = 1; i <= n; i++){if (!dfn[i]) {tarjan(i, 0);}}// 对桥进行排序（按起点升序，起点相同按终点升序）sort(bri + 1, bri + cnt + 1);// 输出所有桥for (int i = 1; i <= cnt; i++){cout << bri[i].x << " " << bri[i].y << endl;}return 0;
}
【运行结果】
6 6
1 2
2 3
2 4
3 5
4 5
5 6
1 2
5 6