题目描述在计算机网络中若存在两台服务器AAA和BBB使得它们之间的所有网络路径都经过某条链路LLL则称LLL为关键链路即桥。移除一条关键链路会将网络分成两个互不相连的子网。给定一个无向图可能不连通要求找出所有关键链路并按第一个端点升序输出。输入格式输入包含多个数据集合每个集合描述一个网络。第一行为一个整数nnn可能为000表示服务器数量。随后nnn行每行格式为u (cnt) v1 v2 ...其中uuu为服务器编号cntcntcnt为直接连接数后面cntcntcnt个整数为相邻服务器编号。输入数据正确。服务器编号从000到n−1n-1n−1。两个数据集合之间无空行分隔以n0n0n0结束。输出格式对于每个数据集合首先输出一行格式为k critical links其中kkk为关键链路数量。然后每行输出一条关键链路格式为u - vuvu vuv按uuu升序若uuu相同按vvv升序排列。每个数据集合输出后跟一个空行。样例输入8 0 (1) 1 1 (3) 2 0 3 2 (2) 1 3 3 (3) 1 2 4 4 (1) 3 7 (1) 6 6 (1) 7 5 (0) 0样例输出3 critical links 0 - 1 3 - 4 6 - 7 0 critical links题目分析求无向图中的所有桥关键链路使用Tarjan\texttt{Tarjan}Tarjan算法基于深度优先搜索DFS\texttt{DFS}DFS计算每个顶点的dfn\textit{dfn}dfn发现时间和low\textit{low}low能回溯到的最早祖先。对于边(u,v)(u, v)(u,v)若dfn[u]low[v]\textit{dfn}[u] \textit{low}[v]dfn[u]low[v]则(u,v)(u,v)(u,v)是桥。算法从每个未访问的顶点开始DFS\texttt{DFS}DFS处理孤立节点和多个连通分量。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入nnn。若n0n 0n0则结束。步骤2\texttt{2}2. 构建邻接表。对每个服务器uuu读入uuu、括号内的cntcntcnt以及cntcntcnt个邻居vvv将uuu和vvv互相加入邻接表。步骤3\texttt{3}3. 初始化dfn\textit{dfn}dfn、low\textit{low}low、visited\textit{visited}visited数组。对于每个未访问顶点uuu调用DFS(u,parent,depth)\texttt{DFS}(u, parent, depth)DFS(u,parent,depth)。步骤4\texttt{4}4.DFS\texttt{DFS}DFS实现标记uuu已访问设置dfn[u]low[u]depth\textit{dfn}[u] \textit{low}[u] depthdfn[u]low[u]depth。遍历邻接顶点vvv若vvv是父节点则跳过。若vvv已访问则更新low[u]min⁡(low[u],dfn[v])\textit{low}[u] \min(\textit{low}[u], \textit{dfn}[v])low[u]min(low[u],dfn[v])。若vvv未访问递归调用DFS(v,u,depth1)\texttt{DFS}(v, u, depth1)DFS(v,u,depth1)然后更新low[u]min⁡(low[u],low[v])\textit{low}[u] \min(\textit{low}[u], \textit{low}[v])low[u]min(low[u],low[v])。若dfn[u]low[v]\textit{dfn}[u] \textit{low}[v]dfn[u]low[v]则(u,v)(u, v)(u,v)是桥加入列表。步骤5\texttt{5}5. 确保每条桥输出时startendstart endstartend。按startstartstart升序、endendend升序排序并输出。代码实现// Critical Links// UVa ID: 796// Verdict: Accepted// Submission Date: 2016-11-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV2010;structedge{intstart,end;booloperator(constedgex)const{if(start!x.start)returnstartx.start;elsereturnendx.end;}};vectorintg[MAXV];vectoredgebridge;intdfn[MAXV],low[MAXV],visited[MAXV];voiddfs(intu,intparent,intdepth){visited[u]1;dfn[u]low[u]depth;for(autov:g[u]){if(v!parentvisited[v]1)low[u]min(low[u],dfn[v]);if(!visited[v]){dfs(v,u,depth1);low[u]min(low[u],low[v]);if(dfn[u]low[v])bridge.push_back((edge){u,v});}}visited[u]2;}intmain(intargc,char*argv[]){intservers;while(cinservers){for(inti0;iservers;i)g[i].clear();string s;for(inti1,u,v,c;iservers;i){cinus;cstoi(s.substr(1,s.length()-2));for(intj1;jc;j){cinv;g[u].push_back(v);g[v].push_back(u);}}bridge.clear();memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(visited,0,sizeof(visited));for(intu0;uservers;u)if(!visited[u])dfs(u,-1,1);for(inti0;ibridge.size();i)if(bridge[i].startbridge[i].end)swap(bridge[i].start,bridge[i].end);coutbridge.size() critical links\n;sort(bridge.begin(),bridge.end());for(inti0;ibridge.size();i)coutbridge[i].start - bridge[i].end\n;cout\n;}return0;}总结本题通过Tarjan\texttt{Tarjan}Tarjan算法在O(VE)O(VE)O(VE)时间内找出无向图的所有桥。关键在于正确维护low\textit{low}low值并利用dfn[u]low[v]\textit{dfn}[u] \textit{low}[v]dfn[u]low[v]判断桥。输入格式中括号内的连接数需解析使用字符串处理提取数字。输出要求按startstartstart升序并保证startendstart endstartend。该算法适用于顶点数多达200020002000的规模效率较高。理解DFS\texttt{DFS}DFS树和回边的关系是解决此类问题的核心。