洛谷 P1656 炸鐵路

題目描述

因為某國被某紅色政權殘酷的高壓暴力統治。美國派出将軍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

求割邊模闆題直接用Tarjan

(我把我部落格裡tarjan求割邊的模闆代碼改改拿過來了)

code：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAX=;
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=;i<=n;i++) if(!dfn[i]) cutedge(i,);
    sort(cedge+,cedge+sum+,cmp);
    for(int i=;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=;i<=m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    find_cutedge();
    return ;
}