图论算法-割点、割边应用

图论算法－割点、割边~apieceofcake~引题我们常常碰到一些求删某条边使其图不连通，或点。如ZJ.PTSC2004的《嗅探器》，如KOJ上的《消息不可走漏》，虽然我们都可以用暴力来解决，但是这个时间复杂平方级别的，一但数据范围扩大，这个就无法解决了。其实这个是有线性算法。概念如果一张无向连通图，在删掉某些点集后这张图就不连通，而删掉这个集合的任意一个真子集，这张图任就是连通的，那么就称这个点集为点割集，如果一个结点就是点割集，那么就称这个结点为割点概念如果一张无向连通图，在删掉某些边集后这张图就不连通，而删掉这个集合的任意一个真子集，这张图任就是连通的，那么就称这个点集为边割集，如果一个结点就是点割集，那么就称这个结点为割边或桥First首先我们必须明白一点，关於图的DFS的性质，我们对图进行DFS遍历，DFS本身是没有什么作用，只用来求连通块，而我们利用的是DFS的遍历顺序。DFS遍历出来的一棵树满足一个特点：对于一个结点的任意两个以其儿子结点为根的子树，必须通过这个结点或者其祖先才能连通，也就是说，在删掉这个结点后，任意两棵以其儿子为根的子树都不互相连通。这个很显然，因为对于一棵子树，如果与其连通，那么就都会遍历到，不然就回溯至其祖先。算法那么在DFS的时候，我们纪录每个儿子子树，与其相连的最高的祖先的层号，如果这个层号>=其父亲的层号,那么删掉这个父亲结点后这棵子树将于其祖先不连通.如果这个层号>其父亲的层号,那么删掉这条连接父亲的边,那么这棵子树将于其祖先不连通.算法那么这个算法也就出来了,只需在DFS时加入求和其相连的最高祖先的语句就行了消息不可走漏(KOJ1047)Description玛莉得知公主被虏走的消息，决定前去营救，所以这个消息坚决不能够被敌人知道了，因为敌人一但得知，告知了每个堡垒后，营救工作一定会非常困难的！！

玛莉窃取了一分地图，里面记载了敌人的n座堡垒，某些堡垒之间修筑了公路。任意两个堡垒都可以通过公路直接或者间接到达。玛莉发现有些公路被毁坏之后会造成某两个城市之间无法互相通过公路到达。只要炸掉这样的一条公路，玛莉就可以完成他的第一步救援计划了。但是，要在短时间内找出来，这是个多么难的问题呀，所以现在玛莉求助于你，希望你能够通过编程，在１秒中内找出这样的公路来。

分析这题是一题割边的应用,当然用复杂度再高点的算法也可以.这题的算法就是割边,是练习割边的基础题.嗅探器(PTSC.ZJ04)某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?嗅探器分析这题显然是求割点,但是这个割点有些不同,这个点割掉只能使a,b不连通,那么怎么做呢?显然这题可以用暴力枚举来实现,复杂度虽然大,但是这题的范围不大,所以还是可以做的分析那怎么用割点来实现呢?很显然问题要求的点一定是这张图的割点,但是割点并不都是这个问题要求的点.我们通过观察割点算法,如果纪录在当前子树是否有a,或者b.那么这些点也就很容易描述了:这个点是割点,且AXorB分析所以在实现时只要在判断是否是割点时加入这个判断语句就可以了.CEOI2005(关键网线问题

)(CriticalNetworkLines)Inputfile:net.in100pointsOutputfile:net.outTimelimit:3secSourcecode:net.pas/.c/.cppMemorylimit:64MB问题描述考虑这样一个通讯网络，它由一些结点和连接结点之间的双向网线组成。已知该连通网络的每对结点之间都存在一条信息流通网路。一些结点向所有结点（包括自己）提供A服务，同时一些结点也向所有结点提供B服务。同一个结点有可能同时提供这两种服务。每个结点都应当能得到这两种服务。如果有一根网线出现问题，可能导致某个结点无法获得某个服务，具备这种性质的网线就称为关键网线。任务目标编一段程序，找出关键网线数（TaskA）以及连接这些网线的两端结点（结点对）（TaskB）。输入数据文件net.in的第一行包含4个整数：总的结点数N(1≤N≤100000)，连接的网线数

M(1≤M≤1000000)，提供A服务的结点数K(1≤K≤N)，提供B服务的结点数L(1≤L≤N)。第二行是K个整数，标明提供A服务的结点。。输入文件第三行是L个整数，标明提供B服务的结点。接下来的M行表示网线的连接位置，每行有两个整数pq(1≤p,q≤N,p≠q)，是网线两端的结点。任意两个结点之间，最多有一条网线相连。输出文件文件net.out的第一行是关键网线的数目S（TaskA）。接下来的S行各含一对整数pq(1≤p,q≤N)，分别定义了一条关键网线（TaskB）关键网线可以按任意顺序输出。每一条关键网线的两个端点也可按任一顺序输出。Examplenet.in

net.out910342454983124123421556676879873325679分析这题,很显然是求桥,但是这个桥有不同之处,并不是只要图不连通就可以了.由题意可知这些边一定是桥,但是桥不一定是这些边.要是某些点得不到某种服务,那么就是要求在其连通块中该没有服务的