題目描述

因為某國被某紅色政權殘酷的高壓暴力統(tǒng)治。美國派出將軍uim，對該國進行戰(zhàn)略性措施，以解救涂炭的生靈。

該國有n個城市，這些城市以鐵路相連。任意兩個城市都可以通過鐵路直接或者間接到達。

uim發(fā)現(xiàn)有些鐵路被毀壞之后，某兩個城市無法互相通過鐵路到達。這樣的鐵路就被稱為key road。

uim為了盡快使該國的物流系統(tǒng)癱瘓，希望炸毀鐵路，以達到存在某兩個城市無法互相通過鐵路到達的效果。

然而，只有一發(fā)炮彈（美國國會不給錢了）。所以，他能轟炸哪一條鐵路呢？

輸入輸出格式

輸入格式：
第一行n，m(1<=n<=150, 1<=m<=5000)，分別表示有n個城市，總共m條鐵路。

以下m行,每行兩個整數(shù)a, b，表示城市a和城市b之間有鐵路直接連接。

輸出格式：
輸出有若干行。

每行包含兩個數(shù)字a,b(a < b)，表示 < a,b > 是key road。

請注意：輸出時，所有的數(shù)對 < a,b > 必須按照a從小到大排序輸出；如果a相同，則根據(jù)b從小到大排序。

輸入輸出樣例

輸入樣例1：
6 6
1 2
2 3
2 4
3 5
4 5
5 6
輸出樣例1
1 2
5 6

求割邊模板題直接用Tarjan
(我把我博客里tarjan求割邊的模板代碼改改拿過來了)

code：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std;const int MAX=1000010; int n,m,cnt,sum; int head[MAX],low[MAX],dfn[MAX],cedge[MAX];struct edg{int to,next,from; }edge[MAX];void add(int x,int y){edge[++cnt].next=head[x];edge[cnt].from=x,edge[cnt].to=y;head[x]=cnt; }void cutedge(int u,int f){dfn[u]=low[u]=++cnt;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){cutedge(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]) cedge[++sum]=i;}else if(v!=f) low[u]=min(low[u],dfn[v]);} }bool cmp(int a,int b){if(edge[a].from==edge[b].from) return edge[a].to<edge[b].to;return edge[a].from<edge[b].from; }void find_cutedge(){for(int i=1;i<=n;i++) if(!dfn[i]) cutedge(i,0);sort(cedge+1,cedge+sum+1,cmp);for(int i=1;i<=sum;i++) printf("%d %d\n",edge[cedge[i]].from,edge[cedge[i]].to); }int main(){scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){int a,b;scanf("%d %d",&a,&b);add(a,b);add(b,a);}find_cutedge();return 0; }

轉載于:https://www.cnblogs.com/Menteur-Hxy/p/9248045.html

總結

以上是生活随笔為你收集整理的洛谷 P1656 炸铁路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。