您好、欢迎来到现金彩票网!
当前位置:秒速快三开奖 > 双连通分支 >

POJ 1523 SPF 无向图求割点和块

发布时间:2019-05-20 11:46 来源:未知 编辑:admin

  题意:给一个无向图,求该无向图中的割点和该割点属于块的数量。一个割点是可以属于多个块的。

  思路:深搜,dfs解决。给出一些无向图中关于割点割边的知识,是从网上找的。

  割点:删掉它之后(删掉所有跟它相连的边),图必然会分裂成两个或两个以上的子图。

  缩点:把没有割边的连通子图缩为一个点,此时满足任意两点间都有两条路径相互可达。

  求块跟求缩点非常相似,很容易搞混,但本质上完全不同。割点可以存在多个块中(假如存在k个块中),最终该点与其他点形成k个块,对无割边的连通子图进行缩点后(假设为k个),新图便变为一棵k个点由k-1条割边连接成的树,倘若其中有一条边不是割边,则它必可与其他割边形成一个环,而能继续进行缩点。

  有割点的图不一定有割边,如:               有割边的图也不定有割点,如:

  强连通分量:有向图中任意两点相互可达的连通子图,其实也十分类似于无向图中的缩点

  借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边,用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。

  如果low[u]=dfn[v],说明v的儿子u不能通过其他边到达v的祖先,此时如果拿掉v,则必定把v的祖先和v的儿子u,及它的子孙分开,于是v便是一个割点,v和它的子孙形成一个块。

  如果low[u]dfn[v]时,则说明u不仅不能到达v的祖先,连v也不能通过另外一条边直接到达,从而它们之间的边w(v,u)便是割边,求割边的时候有一个重边的问题要视情况处理,如果v,u之间有两条无向边,需要仍视为割边的话,则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去,从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中,比如电线连接两台设备A,B 如果它们之间有两根电线,则应该视为是双连通的,因为任何一条电线出问题都不会破坏A和B之间的连通性,这个时候,我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号,在开始遍历v-u前检查它的id是否在上一次u-v时被标记,这样如果两点之间有多条边时,每次遍历都只标记其中一条,还可以通过其他边回去,形成第二条新的路

  求割点的时候,维护一个栈st 每遍历到一个顶点v则把它放进去,对它的子孙u如果dfn[u]为0,则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v],如果low[u]=dfn[v],则把栈中从栈顶到v这一系列元素弹出,这些点与v形成一个块,如果u的子孙x也是一个割点,这样做会不会错把它们和v,u放在一起形成一个块呢,这种情况是不会发生的,如果发现x是一个割点,则DFS到x那一步后栈早就把属于x的子孙弹出来了,而只剩下v,u的子孙,它们之间不存在割点,否则在回溯到v之前也早就提前出栈了!画一个图照着代码模拟一下可以方便理解。

  有向图强连通分量的算法有两个,一个是Kosaraju,另一个是Tarjan,前者需要两次DFS,代码量偏大但容易理解,后者只需要一次DFS和维护一个栈便可以,实现简单,详见这里

  求割点的时候由于不知道最开始选的树根是不是只有一个儿子,这样在DFS过来中不会满足low[u]=dfn[v]而判为割点,但有两个或两个以上儿子的根肯定也是一个割点,所以要特判!

  概念:割点:有一个无向图G,如果删除某个顶点u以后,联通分量的数目增加,称u为图的关节点,或割点。祖先:树形结构的概念,从根到该节点缩经分支上的所有节点。子孙(后代):树形结构的概念,以某节点为根的紫...博文来自:@fei

  部分内容转载自点击打开链接1.相关概念无向连通图:无向图是连通的,当且仅当从任意节点开始的深度优先搜索将会遍历...博文来自:通往花开的路上

  膜你抄(QWQ)“tarjan陪伴强联通分量生成树完成后思路才闪光欧拉跑过的七桥古塘让你心驰神往”----《膜你抄》Tarjan是一种求强连通分量、双连通分量的常用算法,其拓展例如求缩点、割点、割桥以...博文来自:huangdanning的博客(.cpp)

  Tarjan这个人啊,你们可能不太了解,但是,他创造的算法你们一定就听过了——Splay、lct……我们今天来看以他名字命名的图论算法。介绍三个东西。dfn:时间戳没什么好说的。搜索树:dfs这些点的...博文来自:向来缘浅,奈何情深

  首先要明确割点与割边的概念,割点:在一个连通图中,如果去掉了某个点和所有与这个点相连的边后,是图分成了两个部分,变成了一个不连通的图。那么这个点就是割点。割边:在一个连通图中,如果去掉了某个点,把图分...博文来自:lengwuqin的专栏

  一.割点和桥无向连通图中,如果删除某点后,图变成不连通,则称该点为割点。 无向连通图中,如果删除某边后,图变成不连通,则称该边为桥。所以说啊,割点和桥这个概念的应该范围应该只是在无向连通图中的!这...博文来自:Coldplay

  POJ1523SPF链接:题意:给定一个无向连通图,求割点。并计算出去除每个割点后能将图分为多少块。思路:裸的求无向图割点。代码:/*ID:...博文来自:SIOFive的专栏

  题意:给你一个有N个点的network,要你求图中的割点,对应每个割点给出删除该割点之后,图会变成几个不连通的子图。思路:双连通求割点,对于...博文来自:Chris_Home

  强连通分量:简言之就是找环(每条边只走一次,两两可达)孤立的一个点也是一个连通分量 使用tarjan算法在嵌套的多个环中优先得到最大环(最小环就是每个孤立点) 定义:intTime,DFN[N],Lo...博文来自:九野的博客

  题目地址:POJ1523这题猛的一看。。貌似有点难的样子。不过仔细一想,那个每个割点所分成一次子图不就都能找到这个割点一次吗,那么只要记录下它作为割点的次数再+1不就行了。也算是求割点的裸题吧。这个题...博文来自:scf0920

  刻意选取了割点的题来做题意:要找到题中的所有的割点,然后如果删去割点,可以把全图分成几个部分就是使用割点模板关键是题目中的输入输出处理比较麻烦,要注意好细节#include#include#inclu...博文来自:ACdream

  大致题意:   给出一个连通的无向图,求哪些点是割点,对于每个割点,求出去掉这个点后连通分量的个数。如果没有割点的话输出“NoSPFnodes”。思路:求割点用tarjan即可,然后要求删除割点后连通...博文来自:kalilili的专栏

  无向图求割点的问题,仍然是用到Tarjan算法进行深搜,深搜过程中不断更新每个节点的dfn值和low值,对一个父亲节点u和其子节点v,每次搜索完其一个子节点,更新其low值,即节点u能通过一条其后代的...博文来自:ACMiao的博客

  点击打开链接题意:给出无向图,问你哪些是割点并输出将这个点割掉后的图分为几块思路:无向图割点的模版题,只不过再将cnt里的值输出而已#include#include#include#include#i...博文来自:Dan__ge的博客

  题意无向图找出每个割点,然后求出删除这个割点所得的连通分量个数节点编号在1-1000,但没说按顺序给出思路无向图求所有割点是一类经典问题,这篇blog就以这题为例简单介绍一下求解的算法思路我们希望在O...博文来自:luke2834的专栏

  题目链接:SPF题目大意:给你n条边,问哪条边将网路分成了几个子网络(输出所有的情况)。思路:给你的是无向图,直接上求割点的模板。代码:#include#include#include#include...博文来自:nhl19961226的博客

  本题要求出割点,并算出每个割点将图分成几个分支。用tarjan算法求的割点,然后对每个割点,dfs求有多少个分支每点的数是不一定的,我用的set存的点,vector存的图求多少个分支就是:如果i是割点...博文来自:xiaoyu1_1的专栏

  删除一个无向图中的点,能使得原图增加几个连通分量?如果该点是一个孤立的点,那么增加-1个。如果该点不是割点,那么增加0个。如果该点是割点且非根节点,那么增加该点在dfs树中(无反向边连回早期祖先的)的...博文来自:GameRoad

  题目大意:也是给你一个无向连通图,让你求出该无向图的割点,并求出如果去掉这个割点,该无向图会变成几个连通分量。算法思路:赤裸裸的tarjan求割点算法,但cnt数组记录的是去掉该点,连通图的连通分量的...博文来自:huyifan1的博客

  1.无向图的割点求法:利用Tarjan算法思想,若一个点为割点,那么只存在两种情况:(1)该点是根节点,且有两个以上子节点(2)该点不上根节点,但是该点的低位数大于等于DFS数低位数的定义:从该顶点v...博文来自:untilyouydc

  无向连通图的割点、桥泳裤王子原创,转载请注明出处 预备知识:      割点集合      在一...博文来自:tclh123 - 悲剧的泳裤王子

  1.桥:是存在于无向图中的这样的一条边,如果去掉这一条边,那么整张无向图会分为两部分,这样的一条边称为桥也就是说无向连通图中,如果删除某边后,图变成不连通,则称该边为桥2.割点...博文来自:Df_cjc的博客

  题意:给出一个无向图,求割点以及去除这个点后图分为几部分; 思路:割点定义:去掉该点后图将分成几个部分。割点:(1)当k为根节点且有1个分支,则去除该点后图便被分成几个分支。(2)DFN[v] 代码...博文来自:amourjun的专栏

  题目链接:poj1523 题意描述::略分析:求割点的算法很明显的是用tarjan算法,当一条边u---v时有low[v]=dfn[u](表示v不能更新到u更以前的节点)这就直接说明了u点u之前的和...博文

  题目链接:题目大意:问你图中有哪些割点,并且这些割点能将图分成几块思路:因为是无向图且没有重边,tarjan判断下是否为割点就可以了,如果是...博文来自:树先生丶

  割顶和桥:对于无向图G,如果删除某个节点u后,连通分量数目增加,则称u为图的割顶;如果删除某条边后,连通分量数目增加,则称该边为图的桥。对于连通图删除割顶或桥后都会使得图不再连通以下我,我们利用dfs...博文来自:STILLxjy

  Dfn数组记录搜索到该点的时间。Low数组是一个标记数组,记录该点所在的强连通子图所在搜索子树的根节点的Dfn值。以上是有向图的low、dfn定义,实际上无向图与其类似。在实际运用之前,先看下列一些定...博文来自:casperahead的博客

  最简单也是最直接的算法是,删除一个点然后判断连通性,如果删除此点,图不再连通,则此点是割点,反之不是割点(图的连通性一般通过深搜来判定,是否能一次搜索完全部顶点);通过深搜优先生成树来判定。从任一点出...博文来自:haofight的博客

  连通图的割点、割边(桥)、块、缩点,有向图的强连通分量  【本文摘选自百度文库】一、基本概念无向图割点:删掉它之后(删掉所有跟它相连的边),图必然会分裂成两个或两个以上的子图。块:没有割点的连通子图割...博文来自:Fighting!

  基本概念割点:ArticulationPoint在无向连通图中,删除一个顶点v及其相连的边后,原图从一个连通分量变成了两个或多个连通分量,则称顶点v为割点,同时也称关节点(ArticulationPo...博文来自:好记性不如烂笔头的专栏

  定义对于无向连通图G=(V,E),Tarjan算法可以在线性时间内求出无向图的割点和桥。割点:对于x∈V,如果删除某个点x,图的联通分量增多(G分裂为两个或者两个以上的子图),则x为割点。桥  :对于...博文来自:愿岁月如歌

  无向图中割点:去掉这个点连通分量增加。求法:当一个点为树根时,如果他的儿子数量大于一则这个点为割点,(一棵树的根节点有数量大于一的儿子那么去掉树根,这棵树不连通)当这个点u的dfn[u]     很明...博文来自:阿狸的博客

  经过2-3周工作空闲时间,解决了windows7下面远程桌面中无法访问令牌卡/智能卡的问题。    现象是:通过windows远程桌面,任何智能卡如:工商银行优盾/各行业数字证书等设备,无法找到,也就...博文来自:pjxxlpsj的专栏

  具体方法:  原文:经验教训: 1、新建数据库一定要做一次全...博文来自:dear_Alice_moon的专栏

  帐号相关流程注册范围 企业 政府 媒体 其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  一、背景    一直以来,应用的流畅度都关乎着用户的体验性,而体验性好的产品自然而然会受到更多用户的欢迎,所以对于广大的工程师来说,界面的卡顿优化一直是Android应用性能优化的重要一环。而当前应用...博文来自:u012874222的博客

  原文地址:因为需要用,所以才翻译了这个文档。但总归赖于英语水平很有限,翻译出来的中文有可能...博文来自:ymj7150697的专栏

  一个例子高斯混合模型(Gaussian Mixed Model)指的是多个高斯分布函数的线性组合,理论上GMM可以拟合出任意类型的分布,通常用于解决同一集合下的数据包含多个不同的分布的情况(或者是同一...博文来自:小平子的专栏

  下载对应的ffmpeg的动态库:打开文件ffmpeg.cmake文件,会看到有一个第一行,我们需要下载master_20170704打开博文来自:我们的时光!

  最近新搞了openfire 从网上找了很多源码部署的相关文章但都是大同小异,拷贝加修改,我如是按照各个文章版本部署目前最新的3.8.2版本,无一例外,各种报错,头疼死我也,一次次失败,我TMD就想为啥...博文来自:StillCity的专栏

  目前市场上比较多的应用在用户卸载后会弹出意见反馈界面,比如360手机卫士,腾讯手机管家,应用宝等等,虽然本人不太认同其交互方式,但是在技术实现上还是可以稍微研究下的。其实要实现这个功能,最主要的就是监...博文

  此处仅以VS2010为例,详细说明一下如何在VS环境下生成和使用C++的静态库与动态库。Qt下生成和使用静态和动态库后续再讲。 本文仅供初学者参考,如果有问题欢迎大家指正。        首先简单地理...博文来自:luyan的博客

  转载请注明出处:, 来自: shiter编写程序的艺术2.1 视差理论计算机...博文来自:shiter编写程序的艺术

  上面是别人总结的语音识别方向的资料来源...博文来自:xmdxcsj的专栏

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  因为毕设的原因,最近一直在研究Caffe,按照网上自己搭建Caffe的教程无果后,最终参考了happynear与虾米ning的帖子,但是其中遗漏了一些细节。所以特意写一篇文章来记录自己搭建Caffe的...博文来自:小苗苗X的专栏

  4  软件设计   软件设计部分主要包括uboot移植、内核编译、系统移植、设备驱动编程、应用程序编程(QT编程、mysql数据库编程、控制系统编程)、各个模块的功能函数(部分是在windows下面的...博文来自:求是07的专栏

  转载请注明出处:来自:shiter编写程序的艺术 三维重建技术通过深度数据获取...博文来自:shiter编写程序的艺术

  :第19行的那个getchar()的作用是啥,我去掉发现输入多了一行空的。不太明白,请大佬指点!

http://cellmall.net/shuangliantongfenzhi/65.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有