UVa 610 Street Directions
题目描述
根据汽车碰撞监测机构（ACM\texttt{ACM}ACM）的统计，大多数致命交通事故发生在双向街道上。为了减少交通事故造成的伤亡，市长希望将尽可能多的街道改为单行街道。你需要完成这一转换，使得从每个交叉路口出发，驾驶员都能沿着某条路线到达所有其他交叉路口。
给定城市中所有街道的列表（均为双向街道）。每条街道连接两个交叉路口，且不经过其他交叉路口。每个交叉路口最多与四条街道相连，任意一对交叉路口之间最多有一条街道。可能存在只有一条街道连接的交叉路口。你可以假设当所有街道都是双向时，从任意一个目的地都能到达其他任意目的地。
输入格式
输入包含多个测试用例。每个测试用例的第一行包含两个整数nnn和mmm，分别表示交叉路口的数量（2≤n≤10002 \le n \le 10002≤n≤1000）和街道的数量。接下来的mmm行每行包含两个整数，表示一条街道所连接的两个交叉路口编号（编号从111到nnn）。每条街道只列出一次，如果出现i j，则不会出现j i。输入以n = m = 0结束。
输出格式
对于每个测试用例，首先输出该用例的编号（从111开始），然后输出一个空行。接下来，每行输出一个方向分配，格式为i j，表示街道方向从交叉路口iii到jjj。对于无法转换为单行的街道，需要输出两行，分别为i j和j i$。街道列表可以按任意顺序输出。每个测试用例的输出以单独一行#` 结束。
样例
输入
7 10 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 2 5 3 6 7 9 1 2 1 3 1 4 2 4 3 4 4 5 5 6 5 7 7 6 0 0输出
1 1 2 2 4 3 1 3 6 4 3 5 2 5 4 6 4 6 7 7 5 # 2 1 2 2 4 3 1 4 1 4 3 4 5 5 4 5 6 6 7 7 5 #题目分析
本题的核心是无向连通图的方向化问题。给定一个无向连通图，要求将尽可能多的边定向为有向边，同时保证最终的有向图仍然是强连通的（即从任意节点可以到达任意其他节点）。显然，如果一条边是桥（割边），即删除该边会导致图不连通，那么这条边必须保留双向，否则两个连通分量之间将无法相互到达。对于非桥边，由于其两端存在另一条路径，我们可以将其定向为单向，而不会破坏强连通性。因此，问题转化为：识别图中的所有桥，将非桥边定向为任意方向，桥边保留双向。
我们可以采用一种基于“尝试删除”的方法，避免显式计算桥。它遍历每条边的两个方向，尝试删除该方向（即临时从邻接表中移除该有向边），然后检查起点能否到达终点。若删除后仍然连通，说明该方向并非必须保留，可以将其删除（即只保留相反方向），从而实现单向；若删除后不连通，则必须保留该方向，最终表现为双向。这种方法在实现上较为简洁，且能直接输出满足要求的定向方案。
解题思路
存储图：使用邻接表
way存储无向图，每个节点i的邻接表中包含所有与其直接相连的节点编号。由于每条边是无向的，邻接表中会同时存储i->j和j->i两条有向记录。定向过程：遍历每个节点
i的邻接表，对于每条有向记录i->j（其中save = way[i][j]），检查该有向边是否已经被处理过（通过集合broken记录已处理的有向边对）。如果未处理，则尝试将其删除：- 将
way[i][j]临时设为-1（表示该方向不存在）。 - 使用深度优先搜索（DFS\texttt{DFS}DFS）检查从
i出发能否到达save。若可以到达，说明删除该方向后图仍然连通，因此该方向不是必须的，可以永久删除（保持-1），并标记i->save为已处理。 - 若不能到达，说明该方向必须保留，则恢复
way[i][j] = save，并标记该方向已处理，以防止后续再次尝试删除。
- 将
输出：完成所有方向的尝试后，再次遍历邻接表，输出所有仍为正数（未被删除）的有向边。若某条无向边两个方向都被保留，则会输出两行，分别表示两个方向；若只保留一个方向，则只输出一行。
正确性保证：由于非桥边至少有一个方向可以被删除，桥边的两个方向都不能删除，最终结果满足强连通性。算法通过逐一尝试删除每个方向，保证了定向方案的有效性。
复杂度分析
- 对于每条有向边（共2m2m2m条），尝试删除并执行一次DFS\texttt{DFS}DFS，每次DFS\texttt{DFS}DFS的时间复杂度为O(n+m)O(n + m)O(n+m)。
- 总时间复杂度为O(m⋅(n+m))O(m \cdot (n + m))O(m⋅(n+m))，在最坏情况下m=O(n2)m = O(n^2)m=O(n2)，可能较大，但由于n≤1000n \le 1000n≤1000且实际数据较稀疏，该算法在给定时限内可运行通过（参考代码运行时间为0.7500.7500.750秒）。
- 空间复杂度为O(n+m)O(n + m)O(n+m)。
代码实现
// Street Directions// UVa ID: 610// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.750s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<vector<int>>way;intvisited[1001];voiddfs(inti){for(autoe:way[i])if(e>0&&!visited[e]){visited[e]=1;dfs(e);}}boolconnected(inti,intj){memset(visited,0,sizeof(visited));dfs(i);returnvisited[j];}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,m,from,to,cases=0;while(cin>>n>>m,n){cout<<++cases<<"\n\n";way.assign(n+1,vector<int>());for(inti=1;i<=m;i++){cin>>from>>to;way[from].push_back(to);way[to].push_back(from);}set<int>broken;for(inti=1;i<=n;i++)for(intj=0;j<way[i].size();j++){intsave=way[i][j];if(broken.find(i*10000+save)==broken.end()&&broken.find(save*10000+i)==broken.end()){way[i][j]=-1;if(!connected(i,save))way[i][j]=save;elsebroken.insert(i*10000+save);}}for(inti=1;i<=n;i++)for(intj=0;j<way[i].size();j++)if(way[i][j]>0)cout<<i<<' '<<way[i][j]<<'\n';cout<<"#\n";}return0;}总结
本题通过模拟删除有向边并检查连通性的方法，巧妙地实现了无向图的方向化，使得最终有向图保持强连通且单向边数量最大化。该方法避免了显式求桥的复杂算法，实现简单直观，适用于节点数和边数适中的场景。关键点在于理解桥与非桥边在方向化过程中的不同处理方式，以及利用DFS\texttt{DFS}DFS进行连通性检验。此解法也展示了在图上进行“试探-验证”策略的实用性。