P1656 炸铁路

题目描述

A 国派出将军 uim，对 B 国进行战略性措施，以解救涂炭的生灵。

B 国有 n 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。

uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。

然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？

输入格式

第一行 n,m (1≤n≤150，1≤m≤5000)，分别表示有 n 个城市，总共 m 条铁路。

以下 m 行，每行两个整数 a, b，表示城市 a 和城市 b 之间有铁路直接连接。

输出格式

输出有若干行。

每行包含两个数字 a,b，其中 a<b，表示 〈a,b〉 是 key road。

请注意：输出时，所有的数对〈a,b〉 必须按照 a 从小到大排序输出；如果a 相同，则根据 b 从小到大排序。

输入输出样例

输入

6 6
1 2
2 3
2 4
3 5
4 5
5 6

输出

1 2
5 6

炸毁一条路对于一张图来说，本质上就是去掉一条边，不能通过铁路到达就代表这张图不连通了，对于这种去掉之后就可以使整张图不再连通的边，我们称之为割边

这道题的本质就是求出这张图所有的割边。

废话不多说，开始推思路

这里要用到两个数组：

时间戳 dfn

追溯值 low

这两个数组在受欢迎的牛里面里面讲过，这里就不多说了

回到题目，首先要解决的问题就是如何判断现在的这条边是不是割边

首先说结论：x和y两个点，low[y]>dfn[x] 就代表x到y这条边是割边

为什么这么说呢？

如果y的追溯值大于了x的时间戳，也就是y的追溯值在x之后，并且，y追溯到的这个点与x一定不连通，因为如果连通，那么y就会顺着这个点追溯到时间戳更小的点x，到这里，我们不难推出：x与y之间直接连通的边，只有这一条，并且没有间接联通的边。所以，如果low[y]>dfn[x],这条边就是割边

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
int dfn[N];
int vis[N];
int low[N];
struct node{
	int x,y;
};
node c[N];
vector<int>a[N];
int cnt;
int times;
bool cmp(node a,node b){
	return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
void add(int u,int v){
	cnt++;
	c[cnt].x=min(u,v);
	c[cnt].y=max(u,v);
}
void tarjan(int x,int fa){
	vis[x]=1;
	dfn[x]=low[x]=++times;
	for(int i=0;i<a[x].size();i++){
		int y=a[x][i];
		if(dfn[y]==0){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x])add(x,y);//判断割边
		}
		if(y!=fa&&dfn[y]!=0)low[x]=min(low[x],dfn[y]);
	}
}
main(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,i);
	sort(c+1,c+1+cnt,cmp);
	for(int i=1;i<=cnt;i++)printf("%d %d\n",c[i].x,c[i].y);
}