UVa 315 Network

题目描述电话线路公司正在建立一个新的电话电缆网络。他们将几个地点编号为111到NNN连接起来线路是双向的。每个地点都有一个电话交换机。从每个地点都可以通过线路到达其他任何地点图是连通的。当某个地点的电源发生故障时该交换机会停止工作。除了该故障地点本身无法到达外还可能导致其他地点之间无法相互连接。在这种情况下该故障地点被称为关键点critical place\texttt{critical place}critical place即割点。要求编写程序计算网络中所有关键点的数量。输入格式输入文件由多个数据块组成每个数据块描述一个网络第一行地点数量N100N 100N100接下来的若干行每行包含一个地点编号后跟与该地点直接相连的若干个地点编号每个数据块以一行0结束最后一个数据块只有一行N0N 0N0输出格式对于每个数据块最后一个除外输出一行包含关键点的数量。样例输入5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0样例输出1 2题目分析问题的本质这是一个无向连通图的割点articulation point\texttt{articulation point}articulation point计数问题。割点是指删除该顶点及其关联边后图的连通分量数量增加的顶点。关键点图是无向图图是连通的输入保证需要找出所有割点割点的定义在无向连通图中顶点vvv是割点当且仅当删除vvv后图不再连通。经典算法Tarjan\texttt{Tarjan}Tarjan算法Tarjan\texttt{Tarjan}Tarjan算法可以在O(VE)O(VE)O(VE)时间内找到无向图的所有割点。算法基于深度优先搜索DFS\texttt{DFS}DFS引入两个重要概念dfn[u]顶点uuu的深度优先数访问时间戳low[u]顶点uuu及其后代顶点能够回溯到的最早祖先的dfn值割点的判定条件对于DFS\texttt{DFS}DFS树中的顶点uuu根节点如果根节点有至少两个子节点则根节点是割点非根节点如果存在子节点vvv满足low[v] dfn[u]则uuu是割点算法推导在DFS\texttt{DFS}DFS过程中初始化dfn[u] low[u] time对于每个邻接点vvv如果vvv未被访问树边递归访问vvv然后更新low[u] min(low[u], low[v])如果low[v] dfn[u]则uuu是割点非根节点如果vvv已被访问且vvv不是父节点回边更新low[u] min(low[u], dfn[v])如果是根节点且子节点数≥2\geq 2≥2则根节点是割点解题思路步骤一图的存储使用邻接表存储图由于输入可能包含重复边使用setint自动去重。步骤二输入解析输入格式较特殊每行第一个数字是起点后面是该起点的所有邻接点每个数据块以0结束最后一个数据块以0开始并立即结束使用getline逐行读取istringstream解析数字。步骤三Tarjan\texttt{Tarjan}Tarjan算法实现intdfs(intu,intparent){intlowudfn[u]dfstime;intchildren0;for(autov:edges[u]){if(!dfn[v]){// 树边children;intlowvdfs(v,u);lowumin(lowu,lowv);if(lowvdfn[u]parent!-1)ic[u]1;// 非根节点割点条件}elseif(v!parent){// 回边lowumin(lowu,dfn[v]);}}// 根节点割点条件if(parent-1children2)ic[u]1;returnlowu;}步骤四计数输出遍历所有顶点统计ic[i] 1的数量并输出。算法复杂度分析时间复杂度每个顶点访问一次每条边访问两次总复杂度O(VE)O(V E)O(VE)V100V 100V100EEE最多约V2/2V^2/2V2/2完全可行空间复杂度邻接表存储O(VE)O(V E)O(VE)辅助数组O(V)O(V)O(V)总空间复杂度O(VE)O(V E)O(VE)正确性证明引理 1在DFS\texttt{DFS}DFS树中如果非根节点uuu存在子节点vvv满足low[v] dfn[u]则uuu是割点。证明low[v] dfn[u]表示vvv及其后代无法通过回边到达uuu的祖先。因此删除uuu后vvv所在的子树与uuu的祖先部分断开图不再连通。□\square□引理 2如果根节点rrr在DFS\texttt{DFS}DFS树中有至少两个子节点则rrr是割点。证明由于无向图不存在横叉边根的两个子节点之间没有直接路径只能通过根连接。删除根后这两个子节点所在的子树相互断开。□\square□引理 3算法覆盖了所有割点。证明Tarjan\texttt{Tarjan}Tarjan算法的正确性已在图论中得到证明。□\square□参考代码// Network// UVa ID: 315// Verdict: Accepted// Submission Date: 2017-10-21// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 顶点数目最大值constintMAXV110;// 使用邻接表来表示图set 自动去重vectorsetintedges;// dfn: 各顶点的深度优先数访问时间戳// ic: 是否为割点1 表示是割点// dfstime: 时间戳计数器intdfn[MAXV],ic[MAXV],dfstime0;// Tarjan 算法求割点// u: 当前访问的顶点// parent: 父顶点根节点为 -1// 返回顶点 u 的 low 值intdfs(intu,intparent){intlowudfn[u]dfstime;// 初始化 low 值为自身 dfnintchildren0;// 子树计数仅用于根节点// 遍历所有邻接顶点for(autov:edges[u]){if(!dfn[v])// v 未被访问即树边{children;intlowvdfs(v,u);// 递归访问子节点lowumin(lowu,lowv);// 更新 low[u]// 非根节点如果子节点无法回溯到 u 的祖先则 u 是割点if(lowvdfn[u])ic[u]1;}elseif(v!parent)// v 已被访问且不是父节点即回边{lowumin(lowu,dfn[v]);// 用祖先的 dfn 更新 low[u]}}// 根节点如果子节点数 2则是割点if(parent0children1)ic[u]0;returnlowu;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){intnstoi(line);if(n0)break;// 输入结束// 初始化邻接表edges.assign(n1,setint());// 读取数据块istringstream iss;while(getline(cin,line),line!0){iss.clear();iss.str(line);intstart,next;issstart;while(issnext){edges[start].insert(next);edges[next].insert(start);}}// 重置数组dfstime0;memset(ic,0,sizeof(ic));memset(dfn,0,sizeof(dfn));// 从顶点 1 开始 DFS图是连通的dfs(1,-1);// 统计割点数量intcount0;for(inti1;in;i)if(ic[i])count;coutcount\n;}return0;}总结本题的核心在于割点判定使用Tarjan\texttt{Tarjan}Tarjan算法dfn和low数组记录访问时间和最早祖先两种割点条件根节点多子树、非根节点子节点 low 值 ≥ 当前 dfn关键点回顾知识点说明割点定义删除后增加连通分量数dfn[u]深度优先数访问时间low[u]能回溯到的最早祖先的dfn根节点条件子节点数 ≥ 2非根节点条件存在子节点low[v] dfn[u]时间复杂度O(VE)O(VE)O(VE)算法思想的应用Tarjan\texttt{Tarjan}Tarjan算法是图论中的经典算法除了求割点还可以用于求桥bridge\texttt{bridge}bridge强连通分量SCC\texttt{SCC}SCC双连通分量BCC\texttt{BCC}BCC掌握这个算法对于解决图的连通性问题非常有帮助。