P1656 炸铁路（割边模板）

本文主要是介绍P1656 炸铁路（割边模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

割边的定义

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

怎么找割边

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

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

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

~~~~~      若有一条边从 $u$ 走向了 $v$，且 $low[v]<dfn[u]$ 则这条边就是一条割边。为什么？因为 $low[v]<dfn[u]$ 说明从 $v$ 点出发且不经过当前边的情况下永远也到不了 $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

这篇关于P1656 炸铁路（割边模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---