分析:题意:把尽量多的无向边定向,使得最终图保持强连通的特性。
思路:用tarjan缩点,然后除了割边外的都是单向,割边保持双向。
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; const int N=5000+50; const int M=10000+50; int dfn[N],head[N],low[N],belong[N]; bool instack[N]; int in[N],out[N]; struct edge { int u,v,next,cnt; }e[M*2]; int n,m; int cnt,num,index; stack<int>s; void addedge(int u,int v) { e[num].u=u; e[num].v=v; e[num].cnt=-1; e[num].next=head[u]; head[u]=num++; } void init() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(belong,0,sizeof(belong)); memset(instack,false,sizeof(instack)); while(!s.empty()) s.pop(); cnt=index=num=0; } void tarjan(int u,int pre) { dfn[u]=low[u]=++index; instack[u]=true; int v; s.push(u); for(int i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(v==pre)continue; if(e[i].cnt!=-1)continue; e[i].cnt=1; e[i^1].cnt=0; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[v],low[u]); if(low[v]>dfn[u]) { e[i].cnt=e[i^1].cnt=1; } } else if(instack[v]) { low[u]=min(dfn[v],low[u]); } } if(dfn[u]==low[u]) { cnt++; do{ v=s.top(); s.pop(); instack[v]=false; belong[v]=cnt; }while(u!=v); } } int main() { int k=1; while(~scanf("%d%d",&n,&m)&&n+m) { int i,j; init(); int a,b; for(i=0;i<m;i++) { scanf("%d%d",&a,&b); addedge(a,b); addedge(b,a); } for(i=1;i<=n;i++) { if(!dfn[i]) { tarjan(i,i); } } printf("%d\n\n",k++); for(i=0;i<num;i++) { if(e[i].cnt==1) { printf("%d %d\n",e[i^1].v,e[i].v); } } printf("#\n"); } return 0; }