POJ 1515 Street Directions-白红宇

POJ 1515 Street Directions

阅读量：5086 次

发布时间：2019-06-13

本文共 1275 字，大约阅读时间需要 4 分钟。

题意：

一幅无向图将尽量多的无向边定向成有向边使得图强连通无向图保证是连通的且没有重边

思路：

桥必须是双向的因此先求边双连通分量并将桥保存在ans中

每一个双连通分量内的边一定都能够变成有向边（毕竟是圈组成的图）边的定向方式分两种：

1、对于树枝边u->v 假设low[v]>dfn[u]说明v回不到u上面去所以ans应该是v->u的边否则是u->v

2、对于逆向边应该全在ans中由于对于dfs树而言这样的边利于low减小

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;typedef long long LL;#define N 1010#define M 2000010#define inf 2147483647int 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]
              
               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