题目描述根据汽车碰撞监测机构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(nm)O(n m)O(nm)。总时间复杂度为O(m⋅(nm))O(m \cdot (n m))O(m⋅(nm))在最坏情况下mO(n2)m O(n^2)mO(n2)可能较大但由于n≤1000n \le 1000n≤1000且实际数据较稀疏该算法在给定时限内可运行通过参考代码运行时间为0.7500.7500.750秒。空间复杂度为O(nm)O(n m)O(nm)。代码实现// Street Directions// UVa ID: 610// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.750s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorintway;intvisited[1001];voiddfs(inti){for(autoe:way[i])if(e0!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,cases0;while(cinnm,n){coutcases\n\n;way.assign(n1,vectorint());for(inti1;im;i){cinfromto;way[from].push_back(to);way[to].push_back(from);}setintbroken;for(inti1;in;i)for(intj0;jway[i].size();j){intsaveway[i][j];if(broken.find(i*10000save)broken.end()broken.find(save*10000i)broken.end()){way[i][j]-1;if(!connected(i,save))way[i][j]save;elsebroken.insert(i*10000save);}}for(inti1;in;i)for(intj0;jway[i].size();j)if(way[i][j]0)couti way[i][j]\n;cout#\n;}return0;}总结本题通过模拟删除有向边并检查连通性的方法巧妙地实现了无向图的方向化使得最终有向图保持强连通且单向边数量最大化。该方法避免了显式求桥的复杂算法实现简单直观适用于节点数和边数适中的场景。关键点在于理解桥与非桥边在方向化过程中的不同处理方式以及利用DFS\texttt{DFS}DFS进行连通性检验。此解法也展示了在图上进行“试探-验证”策略的实用性。