题解 P1656 【炸铁路】
hsfzLZH1
·
·
题解
此题所求的是无向图中的所有割边。
对于一个联通的无向图，我们可以从一个节点开始，保证一个节点不遍历两次，可以形成一棵 $DFS$ 树，定义遍历到这个节点的次序为这个节点的时间戳（用 $dfn$ 表示），这样的dfn编号有一个神奇的性质：在 $DFS$ 树中，一个节点的时间戳一定小于他的子树中的所有节点。
定义 $low[i]$ 为不经过 $i$ 和父节点的连边在 $DFS$ 树上可以（直接或间接）访问到的最小的时间戳，在更新的时候顺便维护 $low$ 的值。根据 $dfn$ 的性质，如果 $low[child]>dfn[father]$ ，则不经过 $father，child$ 不能访问到更小的时间戳，那么边 $\langle child,father\rangle$就是割边。
代码：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=10010;
int n,m,x,y,index_,dfn[maxn],low[maxn],ans,a;//index_代表当前的时间戳
vector<int>G[maxn];//存边的数据结构：邻接表
struct Edge{int from,to;}edge[maxn];//答案的边，最后需要排序
bool cmp(const Edge a,const Edge b){if(a.from!=b.from)return a.from<b.from;return a.to<b.to;}//答案边的比较函数
inline void add_edge(int x,int y){edge[ans].from=min(x,y);edge[ans].to=max(x,y);ans++;}//在答案中加入一条边
void dfs(int cur,int fa)//cur是当前节点，fa是他的父亲
{
int child;
dfn[cur]=++index_;//计算当前节点的时间戳
low[cur]=dfn[cur];//当前可以访问到的最早时间戳肯定是自己的时间戳
for(int i=0;i<G[cur].size();i++)//遍历cur的所有出点
{
child=G[cur][i];
if(dfn[child]&&child!=fa)low[cur]=min(low[cur],dfn[child]);//如果访问到了不是父亲节点的节点，更新low的值
if(!dfn[child])//如果这个节点之前没有被访问过
{
dfs(child,cur);//进行一次dfs过程
if(dfn[cur]<low[child])add_edge(cur,child);//如果满足条件，在答案序列中加入这条边
low[cur]=min(low[cur],low[child]);//更新low的值
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,i);//图可能不连通，初始时fa是i不会出现问题
sort(edge,edge+ans,cmp);//将答案序列排个序
for(int i=0;i<ans;i++)printf("%d %d\n",edge[i].from,edge[i].to);//输出
return 0;
}
```
同时建议同学们去做一下洛谷的模板题【割点】，注意求割点时应该是 $low[child]\ge dfn[father]$ ，因为如果还是可以遍历到父亲节点的时候这个child也是割点。
-------------
感谢 [@刀与玫瑰](https://www.luogu.org/space/show?uid=135950) 提供的 hack 数据，本代码在有重边时会出错，如：
```
2 2
1 2
2 1
```
此时断开边 $\langle 1,2 \rangle$ ， $1,2$ 两点仍连通，则 $\langle 1,2\rangle$ 不为割边。
处理方法是在遍历一个点的所有出边时，如果在第一次之外还回到了父亲结点，则按像计算儿子结点的方法一样用父亲结点的值更新当前结点的值。
代码如下：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=10010;
int n,m,x,y,index_,dfn[maxn],low[maxn],ans,a;
vector<int>G[maxn];
struct Edge{int from,to;}edge[maxn];
bool cmp(const Edge a,const Edge b){if(a.from!=b.from)return a.from<b.from;return a.to<b.to;}
inline void add_edge(int x,int y){edge[ans].from=min(x,y);edge[ans].to=max(x,y);ans++;}
void dfs(int cur,int fa)
{
int child;
dfn[cur]=++index_;
low[cur]=dfn[cur];
bool vis=false;
for(int i=0;i<G[cur].size();i++)
{
child=G[cur][i];
if(dfn[child])
{
if(child==fa&&!vis)vis=true;
else low[cur]=min(low[cur],dfn[child]);
}
if(!dfn[child])
{
dfs(child,cur);
if(dfn[cur]<low[child])add_edge(cur,child);
low[cur]=min(low[cur],low[child]);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,i);
sort(edge,edge+ans,cmp);
for(int i=0;i<ans;i++)printf("%d %d\n",edge[i].from,edge[i].to);
return 0;
}
```