UVA 610 Street Directions

87 阅读 0 评论 58 点赞

我是靠谱客的博主烂漫香菇，这篇文章主要介绍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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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;
}