UVA 610 Street Directions

题目大意：问最多可以将图中多少条边改造为有向边，使得任意两点间仍可互相到达。

除割边（桥）以外，任何边均可以改造成有向边。

可在Tarjan的过程中记录方案。

如果找到一个边双连通分量，即可将该分量中的边按有向边存储，找到桥之后将其双向存储。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4;
int n,m;
struct data{int to,next;}e[maxn*10];
int head[maxn];
int cnt=0;
int cur=0;
void ins(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int low[maxn];
int dfn[maxn];
int vis[maxn];
int ans[maxn*10];
int top=0;
void tarjan(int u,int fa)
{
vis[u]=1;
dfn[u]=low[u]=++cur;
for(int i=head[u];i;i=e[i].next)
{
int x=e[i].to;
if(vis[x]==1&&x!=fa)
{
if(low[u]>dfn[x])low[u]=dfn[x];
ans[++top]=u;ans[++top]=x;
}
if(vis[x]==0)
{
tarjan(x,u);
if(low[x]<low[u])low[u]=low[x];
if(low[x]>dfn[u])
{
ans[++top]=u;ans[++top]=x;
ans[++top]=x;ans[++top]=u;
}
else
{
ans[++top]=u;ans[++top]=x;
}
}
}
vis[u]=2;
}
int main()
{
int sce=0;
scanf("%d%d",&n,&m);
while(n)
{
sce++;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
top=cur=cnt=0;
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)tarjan(i,-1);
}
printf("%dnn",sce);
for(int i=top;i>=1;i-=2)printf("%d %dn",ans[i],ans[i-1]);
printf("#n");
scanf("%d%d",&n,&m);
}
return 0;
}

最后

以上就是烂漫香菇为你收集整理的UVA 610 Street Directions的全部内容，希望文章能够帮你解决UVA 610 Street Directions所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。