P1656 炸铁路 · znzryb

## 思路讲解

参考题解

[https://www.luogu.com.cn/article/j9njcvee](https://www.luogu.com.cn/article/j9njcvee)

总之就是祖先的low值比祖父的dfs序大的点，说明他不存在其他路径到达祖父节点

```cpp
		// 这个条件满足说明i不存在其他路径到达祖父节点
		if(low[i]>dfsn[fa[i]]){
			ll a=fa[i],b=i;
			if(a>b)
				swap(a, b);
			ans.push_back({a,b});
		}
```

## AC代码

AC

[https://www.luogu.com.cn/record/198829769](https://www.luogu.com.cn/record/198829769)

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=160;
vector<ll> g[MAXN];

ll N,M;
pll edge[5010];
// 该点的dfs序  子孙可以达到的dfsn值最小的点的dfsn
ll dfsn[MAXN],low[MAXN];
// 该点的父节点
ll fa[MAXN];
ll idx=0;
bool vis[MAXN];

ll dfs(int x,int pa){
	fa[x]=pa;
	vis[x]=true;
	dfsn[x]=++idx;
	low[x]=dfsn[x];	// 暂设low[x]为自己的dfsn序
	for(int i=0;i<g[x].size();++i){
		if(!vis[g[x][i]]){
			low[x]=min(dfs(g[x][i],x),low[x]);
		}else if(g[x][i] != pa ){
			// 不是父节点且被访问过的要搞一下
			low[x]=min(dfsn[g[x][i]],low[x]);
		}else if(g[x][i+1]==pa){
			low[x]=min(dfsn[g[x][i]],low[x]);
		}
	}
	return low[x];
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;++i){
		cin>>edge[i].first>>edge[i].second;
	}
	sort(&edge[1], &edge[M+1]);
	for(int i=1;i<=M;++i){
		g[edge[i].first].push_back(edge[i].second);
		g[edge[i].second].push_back(edge[i].first);
	}
	dfs(1,1);
	vector<pll> ans;
	for(int i=1;i<=N;++i){
		// 这个条件满足说明i不存在其他路径到达祖父节点
		if(low[i]>dfsn[fa[i]]){
			ll a=fa[i],b=i;
			if(a>b)
				swap(a, b);
			ans.push_back({a,b});
		}
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();++i){
		cout<<ans[i].first<<' '<<ans[i].second<<'\n';
	}
	return 0;
}
/*
AC https://www.luogu.com.cn/record/198829769
3 3 
1 2 
1 2 
2 3

*/
```

## 心路历程（WA，TLE，MLE……）