mxqz tarjan算法求桥,WA60pts
  • 板块P1656 炸铁路
  • 楼主Greenzhe
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/23 21:41
  • 上次更新2023/10/24 03:14:29
查看原帖
mxqz tarjan算法求桥,WA60pts
552298
Greenzhe楼主2023/1/23 21:41

RT,调了1小时,貌似是反向边建炸了?

#include <bits/stdc++.h>
using namespace std;

int n,m;
int head[10005],ne[100005],ver[100005],tot=1;
int dfn[10005],low[10005],tstamp=0;
map<int,int> bridge;

void add(int x,int y){
	ver[++tot]=y;ne[tot]=head[x];head[x]=tot;
}
void tarjan(int u,int from){
	dfn[u]=low[u]=++tstamp;
	for(int i=head[u];i;i=ne[i]){
		int v=ver[i];
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v])
				bridge.insert({min(u,v),max(u,v)});
		}
		else if(i!=(from^1)){
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	tarjan(1,-1);
	for(auto p:bridge){
		printf("%d %d\n",p.first,p.second);
	}
	return 0;
}

错误数据:

Input:

10 9
2 1
3 1
4 1
10 4
9 4
6 3
7 3
8 3
5 3

Std output:

1 2
1 3
1 4
3 5
3 6
3 7
3 8
4 9
4 10
2023/1/23 21:41
加载中...