发布时间:2026/8/31 18:34:53
P1656 炸铁路【洛谷算法习题】 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;}

相关新闻

2026/8/31 18:34:53

三极管基极-发射极并联电阻的作用、取值与电路设计详解

做硬件开发的朋友,不管是在校学生还是工作几年的工程师,大概率在面试中都遇到过这样一道题: “为什么 NPN 三极管的基极和发射极之间要并联一个电阻?” 第一次看到题目时,很多人会愣一下。教材里画三极管开关电路&am…

2026/8/31 18:34:53

共集电极放大电路完整分析:从静态工作点到仿真实战

分享一套三极管共集电极放大电路的完整分析笔记,从电路结构、静态工作点计算到动态指标推导,再到 Multisim 仿真与实测注意事项,一次讲清楚。无论是准备模电考试,还是在实际项目中用射极跟随器做阻抗变换、缓冲隔离,这…

2026/8/31 18:34:53

测试工程师校招笔试复盘:从等价类到AI测试的备考指南

2018年秋招那阵子,爱奇艺测试工程师的第一场笔试出来后,备考群里的讨论一下子炸了。题目本身不算偏,但很多人栽在同一个地方:用刷算法题的心态去答测试题,结果在等价类、边界值、测试用例设计这些“送分题”上丢了大分…

2026/8/31 18:49:55

备份文件可用性如何持续校验——备份可靠性与长期归档实践

文章目录每日一句正能量1. 背景与问题2. 环境与数据3. 复现过程4. 方案实施自动校验 Shell 脚本示例5. 结果对比7. 常见故障与排查7.1 备份校验失败(sha256sum / pg_verifybackup)7.2 WAL 缺口(归档连续性中断)7.3 恢复脚本报错&a…

2026/8/31 18:49:55

从“能调用”到“可替换”:Coze 多模型 API 编排层设计指南

摘要 当 Coze 工作流同时接入聊天、图片、视频、音频和文件处理接口时,真正的难点往往不是发送一次 HTTP 请求,而是处理不同模型之间的协议差异。即使多个接口使用相同的 Bearer Token、相似的 JSON 请求体,返回字段、状态枚举、流式格式、错…

2026/8/31 18:49:55

Java多线程面试题梳理:从并发原理到线程池实战的3天备考主线

在准备 Java 面试的时候,多线程往往是最容易让人“背了又忘、聊了就崩”的模块。很多候选人能说出 synchronized 是重量级锁、 volatile 能保证可见性,但面试官一旦追问“锁升级的具体过程”“为什么 DCL 单例要加 volatile”“线程池核心线程数怎么…

2026/8/31 18:49:55

STM32上Modbus通信实战:从协议解析到联调踩坑全记录

简介:一份面向 STM32 开发者的 Modbus 通信参考资源包,适合正在学习工业现场总线协议、或需要快速在嵌入式项目中集成 Modbus 功能的工程师。资源以 C 源码为核心,共 107 个文件、4.69MB,包含 48 个 C 源文件、46 个头文件与 2 个…

2026/8/31 18:49:55

嵌入式ROS双系统通信实战:上位机+驱动协同设计与CMake构建

简介:本资源是面向自动驾驶、机器人及ROS开发者的万集716型激光雷达完整驱动与上位机集成方案,聚焦硬件通信、数据解析与ROS系统对接等核心问题,适用于具备嵌入式基础和ROS开发经验的中高级工程师与高校研究者。压缩包共205个文件&#xff0c…

2026/8/31 18:44:55

TouchFree手势交互:从Leap Motion到Windows鼠标事件

简介:TouchFree 1.0.0 是面向Windows平台的手势操控软件,旨在用自然的空中动作取代传统鼠标点击,适合交互设计爱好者、外设开发者以及有无障碍交互需求的用户。软件基于LeapMotion 4.1驱动,以高精度和低延迟捕捉手部动作&#xff…

2026/8/31 1:05:20

vSound小提琴数字处理器实操指南:从接线到演出的完整配置

电小提琴或者原声小提琴插电演出,第一个绕不开的坎就是声音难听。原声琴的共鸣和空气感一旦进了拾音器,出来的往往是一坨干瘪、发尖、带着奇怪塑料味的信号。我当初第一次把琴接上乐队调音台,直接被主唱吐槽"你这声音像在锯钢丝"。…

2026/8/31 2:14:20

传感器接口IC如何攻克生物化学传感的微弱信号难题?

1. 从电极到比特流:为什么生物化学传感必须依赖专用接口IC 做生物化学传感的人都有过类似的经历:明明传感器本身性能很好,信号输出却一塌糊涂——噪声大、漂移明显、重复性差,怎么调都达不到预期。很多时候问题并不在传感器&#…

2026/8/31 1:41:28

STM32F411CEU6多通道ADC采集:扫描模式+DMA实现详解

1. 多通道 ADC 的用武之地把“Multichannel ADC”和“STM32F411CEU6”这两个关键字放在一起,其实就是嵌入式开发里最常遇到的一类需求:用一块不算贵的 MCU,同时采集多路模拟信号。STM32F411CEU6 是 48 引脚的 Cortex-M4F 主控,主频…

2026/8/31 0:07:32

STM32C5设备支持包(IAR DFP)安装指南与常见坑

上一阵子在IAR里折腾一块基于STM32C5系列的新板子,工程从STM32CubeMX导出来之后怎么都编译不过。报错信息很干脆:找不到设备描述文件。跟着错误路径去查,发现指向的是一个让我愣了一下的名字:STMicroelectronics.stm32c5xx.2.1.0.…

2026/8/31 0:07:32

STM32N657 SWO引脚矛盾:CubeMX显示PB3,数据手册为PB5

拿到STM32N657这颗料的第一天,我就撞上了一个让人原地懵圈的引脚矛盾:CubeMX里清清楚楚显示SWO在PB3,翻开数据手册的引脚说明表,却赫然写着PB5。对于一个靠SWO输出调试日志吃饭的人而言,这种"工具和手册打架"…

2026/8/31 12:44:45

实测才敢推 AI论文网站 2026最新测评与推荐

2026年真正好用的AI论文网站,核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。一、综…

2026/8/31 9:19:59

2026必备!AI论文网站测评:最新推荐与深度对比

2026年真正好用的AI论文网站,核心看生成的论文质量、低AI味、格式正确、学术适配四大指标。综合实测,千笔AI、ThouPen、豆包、DeepSeek、Grammarly 是当前最值得推荐的梯队,覆盖从免费到付费、从中文到英文、从文科到理工的全场景需求。 一、…

2026/8/31 6:53:02

摆脱论文困扰!盘点2026年全网爆红的的AI论文写作工具

一天写完毕业论文在2026年已不再是天方夜谭。2026年最炸裂、实测能大幅提速的AI论文写作工具,覆盖选题构思、文献整理、内容生成、格式排版等核心场景,真正帮你高效搞定论文难题。 一、全流程王者:一站式搞定论文全链路(一天定稿首…