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≤1501 ≤ 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 abab表示⟨ 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输入 #16 6 1 2 2 3 2 4 3 5 4 5 5 6输出 #11 2 5 6解题思路本题是图论中的桥割边判定问题要求找出给定无向连通图中哪些边在删除后会使图不再连通即“key road”。由于数据规模较小n ≤ 150 n \le 150n≤150m ≤ 5000 m \le 5000m≤5000可以采用暴力枚举每条边删除该边后用并查集判断剩余图是否连通的方法来求解。1. 问题等价转化桥的定义在无向连通图中若删除某条边后图不再连通则该边称为桥或割边、key road。目标输出图中所有桥。输出顺序需满足每一对( a , b ) (a,b)(a,b)中a b abab所有数对按a aa升序排列若a aa相同则按b bb升序排列。2. 算法实现输入与预处理读入n nn和m mm。对每条边( u , v ) (u,v)(u,v)若u v uvuv则交换确保a b abab的形式。将所有边按u uu升序、若u uu相同按v vv升序排序。排序后按顺序枚举删除边输出的桥自然满足题目要求的顺序。枚举每条边并判断是否为桥对于排序后的第i ii条边将其“删除”即不加入到并查集中。初始化并查集将除第i ii条边外的所有边加入并查集。检查所有节点是否属于同一个集合即图是否连通。可以选择节点1 11作为基准遍历2 ∼ n 2 \sim n2∼n若存在节点与节点1 11不在同一集合则说明图不连通当前删除的边是桥。若为桥输出该边。输出结果因为枚举顺序已经排序直接输出即可。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(nm)存储边和并查集数组。总结本题数据范围允许暴力枚举每一条边通过并查集检查删除该边后图是否连通来判断是否为桥。排序后枚举保证了输出顺序。算法简单直观适用于小规模图。代码简要说明结构体edge存储边的两个端点u , v u,vu,v。排序函数cmp先按u uu升序再按v vv升序。并查集操作fd(x)路径压缩查找根节点。un(x,y)合并两个节点所在集合。主流程读入边并标准化保证u v uvuv。对边排序。枚举第i ii条边构建不包含该边的并查集。检查节点1 11与其他节点是否连通若不连通则输出该边。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structedge{ll u,v;}e[5005];ll fa[155];ll n,m;boolcmp(constedgex,constedgey){if(x.uy.u)returnx.vy.v;returnx.uy.u;}llfd(ll x){if(fa[x]x)returnx;returnfa[x]fd(fa[x]);}voidun(ll x,ll y){ll rxfd(x),ryfd(y);fa[ry]rx;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;im;i){cine[i].ue[i].v;if(e[i].ve[i].u)swap(e[i].u,e[i].v);}sort(e1,em1,cmp);for(ll i1;im;i){for(ll j1;jn;j)fa[j]j;for(ll j1;jm;j)if(j!i)un(e[j].u,e[j].v);for(ll j2;jn;j)if(fd(j)!fd(j-1)){coute[i].u e[i].vendl;break;}}return0;}