企业官网建设流程全解析

P1656 炸铁路

网页链接

P1656 炸铁路

题目描述

A 国派出将军 uim，对 B 国进行战略性措施，以解救涂炭的生灵。

B 国有n nn个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。

uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。

然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？

输入格式

第一行n , m ( 1 ≤ n ≤ 150 n,m\ (1 \leq n\leq 150n,m(1≤n≤150，1 ≤ m ≤ 5000 ) 1 \leq m \leq 5000)1≤m≤5000)，分别表示有n nn个城市，总共m mm条铁路。

以下m mm行，每行两个整数a , b a, ba,b，表示城市a aa和城市b bb之间有铁路直接连接。

保证不存在重边（a , b a, ba,b和b , a b, ab,a也视为重边）。

输出格式

输出有若干行。

每行包含两个数字a , b a,ba,b，其中a < b a<ba<b，表示⟨ a , b ⟩ \lang a,b\rang⟨a,b⟩是 key road。

请注意：输出时，所有的数对⟨ a , b ⟩ \lang a,b\rang⟨a,b⟩必须按照a aa从小到大排序输出；如果a aa相同，则根据b bb从小到大排序。

输入输出样例 #1

输入 #1

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

输出 #1

1 2 5 6

解题思路

本题是图论中的桥（割边）判定问题，要求找出给定无向连通图中，哪些边在删除后会使图不再连通（即“key road”）。由于数据规模较小（n ≤ 150 n \le 150n≤150，m ≤ 5000 m \le 5000m≤5000），可以采用暴力枚举每条边，删除该边后用并查集判断剩余图是否连通的方法来求解。

1. 问题等价转化

• 桥的定义：在无向连通图中，若删除某条边后图不再连通，则该边称为桥（或割边、key road）。
• 目标：输出图中所有桥。输出顺序需满足：每一对( a , b ) (a,b)(a,b)中a < b a<ba<b；所有数对按a aa升序排列，若a aa相同则按b bb升序排列。

2. 算法实现

1. 输入与预处理：
   • 读入n nn和m mm。
   • 对每条边( u , v ) (u,v)(u,v)，若u > v u>vu>v则交换，确保a < b a<ba<b的形式。
   • 将所有边按u uu升序、若u uu相同按v vv升序排序。排序后按顺序枚举删除边，输出的桥自然满足题目要求的顺序。
2. 枚举每条边并判断是否为桥：
   • 对于排序后的第i ii条边，将其“删除”（即不加入到并查集中）。
   • 初始化并查集，将除第i ii条边外的所有边加入并查集。
   • 检查所有节点是否属于同一个集合（即图是否连通）。可以选择节点1 11作为基准，遍历2 ∼ n 2 \sim n2∼n，若存在节点与节点1 11不在同一集合，则说明图不连通，当前删除的边是桥。
   • 若为桥，输出该边。
3. 输出结果：因为枚举顺序已经排序，直接输出即可。

3. 复杂度分析

• 时间复杂度：枚举m mm条边，每次枚举需重新构建并查集并处理其余m − 1 m-1m−1条边，并查集操作近似O ( α ( n ) ) O(\alpha(n))O(α(n))。总复杂度O ( m × ( m ⋅ α ( n ) ) ) ≈ O ( m 2 α ( n ) ) O(m \times (m \cdot \alpha(n))) \approx O(m^2 \alpha(n))O(m×(m⋅α(n)))≈O(m2α(n))。m ≤ 5000 m \le 5000m≤5000，计算量约2.5 × 10 7 2.5\times 10^72.5×107次并查集操作，在时间限制内可行。
• 空间复杂度：O ( n + m ) O(n + m)O(n+m)，存储边和并查集数组。

总结

本题数据范围允许暴力枚举每一条边，通过并查集检查删除该边后图是否连通来判断是否为桥。排序后枚举保证了输出顺序。算法简单直观，适用于小规模图。

代码简要说明

1. 结构体edge存储边的两个端点u , v u,vu,v。
2. 排序函数cmp：先按u uu升序，再按v vv升序。
3. 并查集操作：
   • fd(x)：路径压缩查找根节点。
   • un(x,y)：合并两个节点所在集合。
4. 主流程：
   • 读入边并标准化（保证u < v u<vu<v）。
   • 对边排序。
   • 枚举第i ii条边，构建不包含该边的并查集。
   • 检查节点1 11与其他节点是否连通，若不连通则输出该边。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structedge{ll u,v;}e[5005];ll fa[155];ll n,m;boolcmp(constedge&x,constedge&y){if(x.u==y.u)returnx.v<y.v;returnx.u<y.u;}llfd(ll x){if(fa[x]==x)returnx;returnfa[x]=fd(fa[x]);}voidun(ll x,ll y){ll rx=fd(x),ry=fd(y);fa[ry]=rx;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=1;i<=m;i++){cin>>e[i].u>>e[i].v;if(e[i].v<e[i].u)swap(e[i].u,e[i].v);}sort(e+1,e+m+1,cmp);for(ll i=1;i<=m;i++){for(ll j=1;j<=n;j++)fa[j]=j;for(ll j=1;j<=m;j++)if(j!=i)un(e[j].u,e[j].v);for(ll j=2;j<=n;j++)if(fd(j)!=fd(j-1)){cout<<e[i].u<<" "<<e[i].v<<endl;break;}}return0;}