题意：
一幅无向图 将尽量多的无向边定向成有向边 使得图强连通 无向图保证是连通的且没有重边
思路：
桥必须是双向的 因此先求边双连通分量 并将桥保存在ans中
每一个双连通分量内的边一定都能够变成有向边（毕竟是圈组成的图） 边的定向方式分两种：
1、对于树枝边u->v 假设low[v]>dfn[u]说明v回不到u上面去 所以ans应该是v->u的边 否则是u->v
2、对于逆向边 应该全在ans中 由于对于dfs树而言 这样的边利于low减小
代码：
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<set> #include<vector> using namespace std; typedef long long LL; #define N 1010 #define M 2000010 #define inf 2147483647 int n,m,t=1,tot,idx; int head[N],dfn[N],low[N]; struct edge { int u,v,next; bool vis,cut,left; }ed[M]; void add(int u,int v) { ed[tot].u=u; ed[tot].v=v; ed[tot].next=head[u]; ed[tot].vis=ed[tot].cut=ed[tot].left=false; head[u]=tot++; } void tarjan(int u) { int i,v; dfn[u]=low[u]=++idx; for(i=head[u];~i;i=ed[i].next) { v=ed[i].v; if(ed[i].vis) continue; ed[i].vis=ed[i^1].vis=true; if(dfn[v]==-1) { tarjan(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) { ed[i].cut=ed[i^1].cut=true; ed[i].left=ed[i^1].left=true; } } else low[u]=min(low[u],dfn[v]); } } void dfs(int u) { int i,v; dfn[u]=low[u]=++idx; for(i=head[u];~i;i=ed[i].next) { if(ed[i].cut) continue; v=ed[i].v; if(dfn[v]==-1) { ed[i].vis=ed[i^1].vis=true; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) ed[i^1].left=true; else ed[i].left=true; } else { low[u]=min(low[u],dfn[v]); if(!ed[i].vis) ed[i].left=true; ed[i].vis=ed[i^1].vis=true; } } } void solve() { int i; memset(dfn,-1,sizeof(dfn)); idx=0; tarjan(1); memset(dfn,-1,sizeof(dfn)); idx=0; for(i=0;i<tot;i++) ed[i].vis=false; for(i=1;i<=n;i++) { if(dfn[i]==-1) dfs(i); } } int main() { int i,u,v; while(~scanf("%d%d",&n,&m)) { if(!n&&!m) break; tot=0; memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } solve(); printf("%d\n\n",t++); for(i=0;i<tot;i++) { if(ed[i].left) printf("%d %d\n",ed[i].u,ed[i].v); } printf("#\n"); } return 0; }
转载于:https://www.cnblogs.com/bhlsheji/p/5114213.html
