P1656 炸铁路（割边模板）

      ~~~~~      原题链接       ~~~~~      总题单链接

割边的定义

      ~~~~~      若在一张无向图中，删除一条边后连通块的数量会增加，则这条边是割边。

怎么找割边

      ~~~~~      按 d f s 序 dfs序 dfs序 访问图上的每个点，每个点只访问一遍。

      ~~~~~      对于图上的每个点，记录 d f n [ i ] dfn[i] dfn[i] 表示 点 i i i 第一次被访问到的时间戳， l o w [ i ] low[i] low[i] 表示 点 i i i 不走进入 点 i i i 的反边的情况下能走到的最早时间戳。

      ~~~~~      什么是时间戳？若一个点的时间戳为 x x x，那它就是在 d f s dfs dfs 时第 x x x 个被访问到的点。

      ~~~~~      若有一条边从 u u u 走向了 v v v，且 l o w [ v ] < d f n [ u ] low[v]<dfn[u] low[v]<dfn[u] 则这条边就是一条割边。为什么？因为 l o w [ v ] < d f n [ u ] low[v]<dfn[u] low[v]<dfn[u] 说明从 v v v 点出发且不经过当前边的情况下永远也到不了 u u u 和比 u u u 更早遍历到的点，所以这条边是割边。对这句话理解有问题的同学可以在看一看割边的定义。

模板题代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;

ll head[10005],egt=1;
struct Edge{ll v,nxt;}eg[10005];
inline void adeg(ll u,ll v){
	eg[++egt]={v,head[u]};
	head[u]=egt;
}

ll n,m,tot,cnt;
ll dfn[155],low[155];
vector<pair<ll,ll>>bri;

void Tarjan(ll p,ll ineg){
	dfn[p]=low[p]=++tot;
	for(ll q=head[p];q;q=eg[q].nxt){
		ll v=eg[q].v;
		if(!dfn[v]){
			Tarjan(v,q);
			low[p]=min(low[p],low[v]);
			if(low[v]>dfn[p])bri.push_back({p,v});
		}
		else if(q!=(ineg^1))low[p]=min(low[p],dfn[v]);
	}
}

signed main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	while(m--){
		ll x,y;cin>>x>>y;
		adeg(x,y);adeg(y,x);
	}
	
	Tarjan(1,0);
	
	sort(bri.begin(),bri.end());
	for(pair<ll,ll>it:bri)cout<<it.fir<<" "<<it.sec<<endl;
	
	return 0;
}

      ~~~~~      引用请附名 —— —— —— OMG_NOIP