洛谷P1656 炸铁路

传送门

题目大意：炸毁一条道路使图不连通

题解：tarjian求割边

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 5202
using namespace std;

int n,m,sumedge,tim,cnt;
int head[maxn],low[maxn],dfn[maxn];

struct Ans{
    int x,y;
}ans[maxn];

struct Edge{
    int x,y,nxt;
    Edge(int x=0,int y=0,int nxt=0):
        x(x),y(y),nxt(nxt){}
}edge[maxn<<1];

void add(int x,int y){
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}

bool cmp(Ans a,Ans b){
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}

void Tarjian(int x,int fa){
    low[x]=dfn[x]=++tim;
    for(int i=head[x];i;i=edge[i].nxt){
        int v=edge[i].y;
        if(v==fa)continue;
        if(!dfn[v]){
            Tarjian(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>dfn[x])ans[++cnt].x=x,ans[cnt].y=v;
        }else low[x]=min(low[x],dfn[v]);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++)
     if(!dfn[i])Tarjian(i,i);
    sort(ans+1,ans+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    printf("%d %d
",ans[i].x,ans[i].y);
    return 0;
}