P1656 炸铁路

    • 535通过
    • 1.2K提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 图论 搜索 最短路 模拟 洛谷原创
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim,对该国进行战略性措施,以解救涂炭的生灵。

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

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

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

    然而,只有一发炮弹(美国国会不给钱了)。所以,他能轰炸哪一条铁路呢?

    输入输出格式

    输入格式:

    第一行n,m(1<=n<=150, 1<=m<=5000),分别表示有n个城市,总共m条铁路。

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

    输出格式:

    输出有若干行。

    每行包含两个数字a,b(a<b),表示<a,b>是key road。

    请注意:输出时,所有的数对<a,b>必须按照a从小到大排序输出;如果a相同,则根据b从小到大排序。

    输入输出样例

    输入样例#1: 复制
    6 6
    1 2
    2 3
    2 4
    3 5
    4 5
    5 6
    输出样例#1: 复制
    1 2
    5 6
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。