首页 > 代码库 > 洛谷 P1656 炸铁路
洛谷 P1656 炸铁路
P1656 炸铁路
- 题目提供者kkksc03
- 标签图论搜索/枚举洛谷原创
- 难度普及/提高-
题目描述
因为某国被某红色政权残酷的高压暴力统治。美国派出将军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 61 22 32 43 54 55 6
输出样例#1：
1 25 6
/*20分 未解决 直接暴力 正解Tanjian求桥*/#include<iostream>#include<cstdio>using namespace std;int n,m,f[10010]={0},a[10010]={0};int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); f[x]++; f[y]++; a[x]=y; a[y]=x; } for (int i=1;i<=n;i++) if (f[i]==1) { if (i<a[i]) printf("%d %d\n",i,a[i]); else printf("%d %d\n",a[i],i); } return 0;}
洛谷 P1656 炸铁路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。