图连通性若干拓展问题探讨

图连通性若干拓展问题探讨,北京大学李煜东,引言,BlackHistory去年冬令营营员交流时，我和王启圣上来讲了Robert.E.Tarjan参与发明的斐波那契堆Whythistopic_=dfnu，则u为割点。lowv表示v和v的子树不经过搜索树上的边能够到达的时间戳最小的节点；lowv=dfnu说明从v到以u为根的子树之外的点必须要经过点u；因此u是图中的一个割点。在DFS的过程中，首先递归u的子节点v。从v回溯至u后，检查上述不等式是否成立。若成立，则找到了一个割点u。,求点双连通分量,可以在求割点的过程中维护一个栈求出每个点双连通分量。建立一个栈，存储DFS过程中访问的节点，初次访问一个点时把该点入栈。如果边(u,v)满足lowv=dfnu，即满足了u是割点的判断条件，那么把点从栈顶依次取出，直至取出了点v，取出的这些点和点u一起组成一个点双连通分量。割点可能属于多个点双连通分量，其余点和每条边属于且仅属于一个点双连通分量。因此在从栈中取出节点时，要把u留在栈中。整个DFS结束后，栈中还剩余的节点构成一个点双连通分量。,实现,proceduretarjan(xisavertex)visitxtruedfnxlowxnumnum+1pushxintostacksforeachedge(x,y)fromxdoifnotvisitythentarjan(y)lowxmin(lowx,lowy),iflowy=dfnxthenmarkxasacut-vertexrepeatztopofstackspopzfromstacksuntilz=ymarkvertexesjustpopedandxasaDCCelselowxmin(lowx,dfny),KnightsoftheRoundTable,国王要在圆桌上召开骑士会议，但是若干对骑士之间互相憎恨。出于各种各样奇怪的原因，每次开会前都必须对出席会议的骑士有如下要求：相互憎恨的两个骑士不能坐在相邻的2个位置；为了让投票表决议题时都能有结果（不平票），出席会议的骑士数必须是奇数。如果有某个骑士无法出席任何会议，则国王会为了PeaceoftheWorld把他踢出骑士团。现在给定骑士总数n(ndfnu说明从以v为根的子树到子树之外必须要经过边(u,v)，因此(u,v)是桥。可以像求割点一样，当v回溯至u后，判断上述不等式是否成立。另一种判断方法：当递归v结束时，如果lowv=dfnv说明v和v的父节点之间的边是桥。P.S.在有重边的图上求桥，需要注意对这些重边加以区分。,求边双连通分量,边双连通分量的求法非常简单，只需在求出所有的桥以后，把桥边删除。此时原图分成了若干个连通块，每个连通块就是一个边双连通分量。桥不属于任何一个边双连通分量；其余的边和每个顶点都属于且仅属于一个边双连通分量。,实现,proceduretarjan(xisavertex)visitxtruedfnxlowxnumnum+1foreachedge(x,y)fromxdoifnotvisitythentarjan(y)lowxmin(lowx,lowy),iflowydfnxthenmarkedge(x,y)asabridgeelseifedge(x,y)notonDFStreethenlowxmin(lowx,dfny)/thefollowingstepcanalsofindbridgesifdfnx=lowxthenmarkedgeintoxonDFStreeasabridge,边双连通分量的构造,任意给定一个无向连通图，最少添加多少条边可以把它变为边双连通图？求出所有的桥和边双连通分量，把每个双连通分量缩为一个点。此时的图只包含缩点后的双连通分量和桥边，是一棵无根树。统计树中度数为1的节点的个数cnt。把树变为边双连通图，至少需要添加(cnt+1)/2条边。构造方法：每次寻找最近公共祖先最远的两个度数为1的节点，在两点之间连一条边。这样可以使这两个点到LCA的路径上的所有点形成环，环一定是双连通的。,故乡的梦,不知每日疲于在城市的水泥森林里奔波的你会不会有时也曾向往过乡村的生活。你会不会幻想过，在夏日一个静谧的午后，你沉睡于乡间路边的树荫里，一片叶子落在了你的肩上，而你正做着一个悠长的梦，一个没有城市的梦。我们的问题，正围绕着这个梦境展开从Azure求学的城市到Azure家乡的村庄由若干条路径连接，为了简化起见，我们把这些路径抽象成一个N个节点的无向图，每个节点用一个1,N内的整数表示，其中城市在S节点，Azure的故乡在T节点。在某些节点对(x,y)之间会有双向道路连接，道路的长度为c。不过最近某些道路可能会在施工，Azure想知道，假如某条道路被施工而不能通行的话，他到故乡的最短路经的长度为多少（多次询问）。,故乡的梦,第一行两个正整数N和M，分别表示结点数和道路数。之后M行，每行三个正整数x,y,c，表示在x和y之间存在一条长度为c的道路。之后一行包含两个正整数S和T，表示Azure所在位置和故乡的位置。之后一行包含一个整数Q，表示询问的数目。之后Q行，每行两个整数u和v，表示Azure想知道如果连接u和v之间的道路进入了维修状态，从S到T的最短距离会变为多长。N,m,Q=200000.,故乡的梦,首先用堆优化的Dijkstra算法求出各个点到起点S和终点T的最短路。然后BFS求出最短路径图（所有满足DistSu+w(u,v)=DistSv的边构成的图）。从图中去掉无用节点（把满足上面条件的边(u,v)看做有向边时不能到达T的点）。使用经典Tarjan算法求出图中的桥，并找出所有的边双连通分量。由最短路径图的性质，这些双连通分量可以一字排开，相邻两个之间由桥边连接。,故乡的梦,对于不删除桥边的询问，最短路不变，答案就是DistST。如果删除了桥边，就离线采用以下做法求出所有此类询问的答案：建立一个小根堆，在堆中存储一些边，边(u,v)对应的值为DistSu+w(u,v)+DistTv.依次扫描到每个双连通分量。到达一个DCC后，首先在堆中删除前面的DCC出发到这个DCC的边，然后在堆中添加这个DCC出发到后边DCC的边。堆中的最小值就是“删除掉当前连通块和下一个连通块之间的关键边”时的答案。整个算法的复杂度为O(N+M+Q)logN)。,最近公共祖先,离线处理：读入所有的询问（可使用邻接表存储）。给每个节点添加一个颜色标记，尚未访问的标记为0，进入递归而未回溯的节点标记为1，已经访问过的标记为2。维护一个并查集，访问完某个节点时，就合并该节点所在的集合与其父节点所在的集合。正在处理点u时，u和u的所有祖先的标记均为1，已经访问过的节点均与父节点相连；因此遍历子树u后，考虑所有与u相关的询问lca(u,v)，那么lca(u,v)就是v所在并查集的根。,经典Tarjan算法求LCA,proceduretarjan(xisavertex)faxx,colorx1foreachedge(x,y)fromxdoifcolory=0thentarjan(y),fayxforeachquery(x,y)fromxdoifcolory=2thenanswerofquery(x,y)get(y);colorx2;,Network,Anetworkadministratormanagesalargenetwork.ThenetworkconsistsofNcomputersandMlinksbetweenpairsofcomputers.Anypairofcomputersareconnecteddirectlyorindirectlybysuccessivelinks,sodatacanbetransformedbetweenanytwocomputers.Theadministratorfindsthatsomelinksarevitaltothenetwork,becausefailureofanyoneofthemcancausethatdatacantbetransformedbetweensomecomputers.Hecallsuchalinkabridge.Heisplanningtoaddsomenewlinksonebyonetoeliminateallbridges.Youaretohelptheadministratorbyreportingthenumberofbridgesinthenetworkaftereachnewlinkisadded.,Network,Theinputconsistsofmultipletestcases.EachtestcasestartswithalinecontainingtwointegersN(1N100,000)andM(N-1M200,000).EachofthefollowingMlinescontainstwointegersAandB(1ABN),whichindicatesalinkbetweencomputerAandB.Computersarenumberedfrom1toN.Itisguaranteedthatanytwocomputersareconnectedintheinitialnetwork.ThenextlinecontainsasingleintegerQ(1Q1,000),whichisthenumberofnewlinkstheadministratorplanstoaddtothenetworkonebyone.Thei-thlineofthefollowingQlinescontainstwointegerAandB(1ABN),whichisthei-thaddednewlinkconnectingcomputerAandB.,Network,使用Tarjan算法求出图中所有的桥；找到图中的每一个双联通分量，缩成一个点，此时图变成了一棵树；每次加入一条边(x,y)，相当于x到lca(x,y)、y到lca(x,y)和(x,y)这条边构成了一个环；在环上的边都不是割边，于是可以给这些边打上标记，并更新割边个数。当然以前标记过的边就不要重复计算了；处理环的过程中，对于标记过的边可用并查集路径压缩加以优化，不重复经过以保证时间。思考：在仙人掌上多次询问两点之间的最短路径？,TrafficRealTimeQuerySystem,CityCisreallyanightmareofalldriversforitstrafficjams.Tosolvethetrafficproblem,themayorplanstobuildaRTQS(RealTimeQuerySystem)tomonitoralltrafficsituations.CityCismadeupofNcrossingsandMroads,andeachroadconnectstwocrossings.Allroadsarebidirectional.OneoftheimportanttasksofRTQSistoanswersomequeriesaboutroute-choiceproblem.Specifically,thetaskistofindthecrossingswhichadriverMUSTpasswhenheisdrivingfromonegivenroadtoanothergivenroad.,TrafficRealTimeQuerySystem,ThefirstlinecontainstwointegersNandM.（0N=10000,0M=100000）ThenextMlinesdescribetheroads.InthoseMlines,theithline(istartsfrom1)containstwointegersXiandYi,representingthatroadiconnectscrossingXiandYi(XiYi).ThefollowinglinecontainsasingleintegerQ.（0Qsemibestancxthenbestxbestancxancxy,returny,算法实现,proceduretarjanforytstep-1until1doxfayforeachzinpreidydozdfnzifz=0thencontinueget(z)semiymin(semiy,semibestz)pushyintothebackofdomsemiy,ancyxforeachzindomxdoget(z)ifsemibestzxthenidomzbestzelseidomzxemptydomxfori2step1untilt+1doifidomisemiithenidomiidomidomipushiintothebackofdomidomiidom10,例题,首先是可以用来求有向图的割点（SPOJBIA）。Problem：Entrapment（SPOJEN）冬令营讲义第124页题目大意：有向图，求起点S到终点T的所有路径中最接近源的必经点。Lengauer-Tarjan算法求DominatorTree，得到S到T的必经点，找最近的一个。也可以用网络流，拆点构图，增广两次，第二次增广能够到达的最远点就是答案。,有向图的桥边,给定一张FlowGraph(G,r)，若去掉图中的一条边e后，r不能到达图中的全部节点，则称e是(G,r)的桥。给定一张有向图G和图中的两个点S、T，若图中的一条边e处于从S到T的所有路径上，则称e是从S到T的必经边。有向无环图上的必经边？有向图(可能有环)上的桥边？注意在环上的边可能也是桥，因此不能简单地缩点转化为DAG。,有向图的桥边,有向无环图上的必经边？求S到每个点的路径条数CntS，每个点到T的路径条数CntT；若边(u,v)满足CntSu*CntTv=CntST，则(u,v)是从S到T的必经边；可以对几个大质数取模做上述计算。有向图(可能有环)上的桥边？在一条边uv的中间加一个点，变成uwv，然后用Lengauer-Tarjan算法求有向图的割点，若一个新加的点是割点，则对应的边是割边。,PKUACMTeamsExcursion,ItisatraditionalactivityforPKUACMTeamtogohikingduringthesummertrainingcamp.Thecoachhasfoundanationalparkandacquiredthemapofthispark.Inthismap,therearenintersections(numberedfrom0ton-1)connectedbymone-wayroads,andthemapoftheparkisaDirectedacyclicgraph.Theexcursionwillbeginatacertainstartingintersectionsandendatacertaindestinationintersectiont.Youcanfindaroutefromintersectionstot.Aroadiscalledabridgeifandonlyifyoucannotfindaroutefromstartingintersectiontodestinationonceitdisappears.Theotherordinaryroadsarenotbridgessotheyarenotdangerousatall.Accordingtotheexperienceofthetourists,thedangerlevelofabridgeisequaltoitslength.,PKUACMTeamsExcursion,Thenationalparkprovidesanexpressservice.Thehikerscanorderatmosttwobusesbeforehandtohelpthemtoescapesomeofthemostdangerousroutes.Eachbuscanstartfromanywhere(anyintersectionoranypointonanyroad)inthenationalpark.Butthebusispoweredbyelectricitysoitcanonlytravelnomorethanqmeterscontinuouslyandthepassengershouldgetoffbeforetheelectricityrunsout.Whentheteamisonabus,thedangerlevelalongtheroutecanbeignored.Theproblemisreducedtofindaroutefromthestartintersectiontotheendwiththeleastsumofdangerlevels.Onthewaywecantaketwospecialbusestomakeourroutesafe.1n100000,1m200000,0s,tn,st,1q1000000000,PKUACMTeamsExcursion,题目要求有向无环图中的一条危险程度最小的路径，开始节点和终止节点已经被指定。对于一条边，当它成为“桥”的时候，这条边被标记为危险，危险程度等于边的长度。可以选择搭乘两次车，每次连续行驶不超过q米，在车上经过的桥不计入路径的危险程度。对于这道题目，我们首先用前面提到的计算路劲条数+取模的方法求出S到T的必经边。由于S到T的任何一条路径都包含所有必经边，根据贪心，可以任取一条S到T的最短路。把最短路上的点和边取出，就转化为了一个线性问题，用两段区间尽可能覆盖上面的桥。正向、反向各扫描一遍，求出S,x和x,T上搭一次车的最小危险度，枚举切点x即可。,DisjointSpanningTree,ShannonSwitchingGame,MinimumSpanningTrees,Edge-disjointSpanningTree,ShannonSwitchingGame,Problem：GameofConnect冬令营讲义第125页给定一张无向图和两个特定点A和B，图中的每条边可被染色或者删除。有两个玩家，代号分别为ShortPlayer和CutPlayer，轮流操作。Short每次可以选择一条边染色，Cut每次可以删除一条尚未染色的边。如果最终A和B不再连通，Cut获胜；如果最终从A到B有一条被染色的路径，Short获胜。,GameTime!,通过玩这个Demo的经验，你觉得怎样做才能获胜？,局面与必胜策略,ShannonSwitchingGame只有三种局面：Short有必胜策略、Cut有必胜策略、先手有必胜策略。ShortPlayer有必胜策略，当且仅当图中存在一个连接A和B的子图，子图中存在两棵边不相交的生成树。此时如果Cut删除了一条边使得其中一棵生成树断开分成了两棵子树，Short只需要在另一棵生成树中找到一条连接这两棵子树的边染色。除此之外，其它必胜情况可以考虑图中是否有两棵生成树仅有一条公共边。,EdgeDisjointSpanningTree,从ShannongSwitchingGame的必胜策略出发，我们讨论以下几个问题：MinimumSpanningTrees问题：求带边权无向图G中k棵边不相交的生成树，并且生成树的边权之和尽量小。（Asetofkdisjointspanningtreessuch-thatthetotalvalueoftheedgesisminimum）求无向图G中边不相交的生成树的最多个数（AmaximumnumberofspanningtreesinGwhicharepairwiseedge-disjoint）,MinimumSpanningTrees,问题概述：给定无向图G=(V,E)和一个正整数k，G中的每条边都有一个权值。求无向图G的k棵生成树，满足生成树两两之间没有公共边，并且生成树上所有边的权值之和最小。边不相交生成树：edge-disjointspanningtrees边不相交生成森林：edge-disjointspanningforest解决问题主要在于求出这k棵生成树的边集，基本思想是按边权排序后，贪心地尝试把每条边加入到边集中，并检测加入之后边集还能否分成k个边不相交的生成森林。理论依据来自于拟阵(matroid)。,Var,增广序列(AugmentingSequence),增广(Augmentation),增广的实际意义,寻找增广序列,BFS的结果,第二种情况的进一步思考,三条性质的证明,Clump,并查集维护,算法整体实现,宽搜具体实现(1),宽搜具体实现(2),其它问题,知识扩充篇图灵机与计算复杂性理论,图灵机、递归定理、可归约性、时间复杂性与空间复杂性,生命科学中的一个悖论,（1）生物都是机器；这是现代生物学的宗旨之一，生物体可以看做是以机械方式运作的。（2）生物都能自再生；显然，自再生（繁殖）是生物物种的本质特征。（3）机器都不能自再生；设计生产线比设计它制造的东西复杂，因为生产线的设计包含其制造物品的设计。因此没有机器能够制造自己，故机器不可能自再生。,引入,机器可以制造自己吗？如何制造？请大家思考这样一个问题：编写一段C+程序，该程序打印出自身。（程序的代码和输出是完全一样的）可以在纸上尝试一下,抽象化,在前几天的课程中，乔明达大神给大家讲解了正则语言、DFA与NFA。而程序设计语言中的语法大多是上下文无关文法，可以用附带一个栈的自动机下推自动机（PDA）来识别。我们称一个机器的实现方法叙述为它的“描述”。由于丘奇-图灵论题告诉我们，算法的定义等价于图灵机描述，因此我们来考虑：制造一个图灵机，该图灵机打印出自己的描述。,初识图灵机,图灵机(TM)是一种通用的计算机模型，它与有穷自动机类似，但是具有无限大容量的存储和任意访问内部数据的能力。图灵机具有一个无限长的纸带，开始运行时带上只有输入串，其余位置为空；图灵机具有一个双向读写头，可以纸带上左右移动，读取或者修改纸带上的信息；图灵机预置接受和拒绝两种状态，一旦进入则立即停机，没有进入则持续运行永不停止；与有穷自动机类似，分为确定型（DTM）