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