题目描述
在计算机网络中，若存在两台服务器AAA和BBB，使得它们之间的所有网络路径都经过某条链路LLL，则称LLL为关键链路（即桥）。移除一条关键链路会将网络分成两个互不相连的子网。给定一个无向图（可能不连通），要求找出所有关键链路，并按第一个端点升序输出。
输入格式
输入包含多个数据集合，每个集合描述一个网络。第一行为一个整数nnn（可能为000），表示服务器数量。随后nnn行，每行格式为：u (cnt) v1 v2 ...，其中uuu为服务器编号，cntcntcnt为直接连接数，后面cntcntcnt个整数为相邻服务器编号。输入数据正确。服务器编号从000到n−1n-1n−1。两个数据集合之间无空行分隔，以n=0n=0n=0结束。
输出格式
对于每个数据集合，首先输出一行，格式为k critical links，其中kkk为关键链路数量。然后每行输出一条关键链路，格式为u - v（u<vu < vu<v），按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。若n=0n = 0n=0，则结束。
步骤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,depth+1)\texttt{DFS}(v, u, depth+1)DFS(v,u,depth+1)，然后更新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. 确保每条桥输出时start<endstart < endstart<end。按startstartstart升序、endendend升序排序并输出。
代码实现
// Critical Links// UVa ID: 796// Verdict: Accepted// Submission Date: 2016-11-30// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=2010;structedge{intstart,end;booloperator<(constedge&x)const{if(start!=x.start)returnstart<x.start;elsereturnend<x.end;}};vector<int>g[MAXV];vector<edge>bridge;intdfn[MAXV],low[MAXV],visited[MAXV];voiddfs(intu,intparent,intdepth){visited[u]=1;dfn[u]=low[u]=depth;for(autov:g[u]){if(v!=parent&&visited[v]==1)low[u]=min(low[u],dfn[v]);if(!visited[v]){dfs(v,u,depth+1);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(cin>>servers){for(inti=0;i<servers;i++)g[i].clear();string s;for(inti=1,u,v,c;i<=servers;i++){cin>>u>>s;c=stoi(s.substr(1,s.length()-2));for(intj=1;j<=c;j++){cin>>v;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(intu=0;u<servers;u++)if(!visited[u])dfs(u,-1,1);for(inti=0;i<bridge.size();i++)if(bridge[i].start>bridge[i].end)swap(bridge[i].start,bridge[i].end);cout<<bridge.size()<<" critical links\n";sort(bridge.begin(),bridge.end());for(inti=0;i<bridge.size();i++)cout<<bridge[i].start<<" - "<<bridge[i].end<<'\n';cout<<'\n';}return0;}总结
本题通过Tarjan\texttt{Tarjan}Tarjan算法在O(V+E)O(V+E)O(V+E)时间内找出无向图的所有桥。关键在于正确维护low\textit{low}low值，并利用dfn[u]<low[v]\textit{dfn}[u] < \textit{low}[v]dfn[u]<low[v]判断桥。输入格式中括号内的连接数需解析，使用字符串处理提取数字。输出要求按startstartstart升序，并保证start<endstart < endstart<end。该算法适用于顶点数多达200020002000的规模，效率较高。理解DFS\texttt{DFS}DFS树和回边的关系是解决此类问题的核心。
