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

引言•BlackHistory……•去年冬令营营员交流时，我和王启圣上来讲了Robert.E.Tarjan参与发明的斐波那契堆……•Whythistopic_？•今年有幸再次来WC，本着继续膜拜Tarjan的一种精神，于是决定把Tarjan主要研究的方向之一——图连通性作为主题。•这部分内容难度本身就不大，所以希望大家度过一个愉悦的上午。。。（什么？你说后缀仙人掌和函数式LCT也愉♂悦？别闹了那不是一种愉悦好么……）安排•第一节课-知识普及-8:00~9:00•无向图连通性（面向NOIP选手）•第二节课-主要内容-9:00~9:15、9:30~10:45•有向图连通性、DominatorTree、ShannonSwitchingGame、DisjointSpanningTree•第三节课-拓展讨论-11:00~12:00•图灵机与计算复杂性理论（知识扩充）无向图连通性无向图的割点、桥、双连通分量；经典Tarjan算法需要解决的问题•无向图的割点、割点集合与点连通度•无向图的桥、割边集合与边连通度•无向图的割点与点双连通分量的求法•无向图的桥与边双连通分量的求法、边双连通分量的构造•使用Tarjan算法求最近公共祖先•相关例题讨论割点•在无向连通图G上进行如下定义：•割点：若删掉某点P后，G分裂为两个或两个以上的子图，则称P为G的割点。•割点集合：在无向连通图G中，如果有一个顶点集合，删除这个顶点集合以及与该点集中的顶点相关联的边以后，原图分成多于一个连通块，则称这个点集为G的割点集合。•点连通度：最小割点集合的大小称为无向图G的点连通度。割边•类似地，在无向连通图G上进行如下定义：•桥(割边)：若删掉某条边B后，G分裂为两个或两个以上的子图，则称B为G的桥(割边)。•割边集合：如果有一个边集合，删除这个边集以后，原图分成多于一个连通块，则称这个边集为割边集合。•边连通度：最小割边集合的大小称为无向图G的边连通度。双连通分量•点双连通图：点连通度大于1的图称为点双连通图（没有割点）。•边双连通图：边连通度大于1的图称为边双连通图（没有割边）。•无向图G的极大(点/边)双连通子图称为(点/边)双连通分量。•缩点：把一个双连通分量缩为一个点的过程，就是删除与该双连通分量相关的所有点和边，然后新建一个点，向所有与双连通分量中的点有边相连的点连边。无向图上的经典Tarjan算法•Tarjan基于对图的深度优先搜索，并对每个节点引入两个值：•dfn[u]：节点u的时间戳，记录点u是DFS过程中第几个访问的节点。•low[u]：记录节点u或u的子树不经过搜索树上的边能够到达的时间戳最小的节点。•对于每一条与u相连的边(u,v)：•若在搜索树上v是u的子节点，则更新low[u]=min(low[u],low[v])；•若(u,v)不是搜索树上的边，则更新low[u]=min(low[u],dfn[v])；求割点•对于一条搜索树上的边(u,v)，其中u是v的父节点，若low[v]=dfn[u]，则u为割点。•low[v]表示v和v的子树不经过搜索树上的边能够到达的时间戳最小的节点；•low[v]=dfn[u]说明从v到以u为根的子树之外的点必须要经过点u；•因此u是图中的一个割点。•在DFS的过程中，首先递归u的子节点v。从v回溯至u后，检查上述不等式是否成立。若成立，则找到了一个割点u。求点双连通分量•可以在求割点的过程中维护一个栈求出每个点双连通分量。•建立一个栈，存储DFS过程中访问的节点，初次访问一个点时把该点入栈。•如果边(u,v)满足low[v]=dfn[u]，即满足了u是割点的判断条件，那么把点从栈顶依次取出，直至取出了点v，取出的这些点和点u一起组成一个点双连通分量。•割点可能属于多个点双连通分量，其余点和每条边属于且仅属于一个点双连通分量。因此在从栈中取出节点时，要把u留在栈中。•整个DFS结束后，栈中还剩余的节点构成一个点双连通分量。实现proceduretarjan(xisavertex){visit[x]←truedfn[x]←low[x]←num←num+1pushxintostacksforeachedge(x,y)fromxdoifnotvisit[y]then{tarjan(y)low[x]←min(low[x],low[y])iflow[y]=dfn[x]then{markxasacut-vertexrepeatz←topofstackspopzfromstacksuntilz=ymarkvertexesjustpopedandxasaDCC}}elselow[x]←min(low[x],dfn[y])}KnightsoftheRoundTable•国王要在圆桌上召开骑士会议，但是若干对骑士之间互相憎恨。出于各种各样奇♂怪的原因，每次开会前都必须对出席会议的骑士有如下要求：•①相互憎恨的两个骑士不能坐在相邻的2个位置；•②为了让投票表决议题时都能有结果（不平票），出席会议的骑士数必须是奇数。•如果有某个骑士无法出席任何会议，则国王会为了PeaceoftheWorld把他踢出骑士团。•现在给定骑士总数n(n=1000)，以及m(m=1000000)对相互憎恨的关系，求至少要踢掉多少个骑士？KnightsoftheRoundTable•题目大意：给定若干骑士和他们之间的仇恨关系，规定召开圆桌会议时，两个有仇恨的骑士不能坐在相邻位置，且召开一次圆桌会议的骑士人数必须为奇数，求有多少骑士永远不可能参加某一次圆桌会议。•模型转化：建补图——没有仇恨的骑士间连边。•几个骑士可以召开圆桌会议的条件是它们构成一个奇环。•问题转化为：求有多少个骑士不包含在任何奇环内。KnightsoftheRoundTable•引理：若某个点双连通分量中存在奇环，则该点双联通分量中的所有点都在某个奇环内。•用经典Tarjan算法找出所有点双联通分量。•判定每个点双联通分量是不是二分图，就可以知道它有没有奇环。求桥•对于一条搜索树上的边(u,v)，其中u是v的父节点，若low[v]dfn[u]，则(u,v)是桥。•low[v]表示v和v的子树不经过搜索树上的边能够到达的时间戳最小的节点；•low[v]dfn[u]说明从以v为根的子树到子树之外必须要经过边(u,v)，因此(u,v)是桥。•可以像求割点一样，当v回溯至u后，判断上述不等式是否成立。•另一种判断方法：当递归v结束时，如果low[v]==dfn[v]说明v和v的父节点之间的边是桥。•P.S.在有重边的图上求桥，需要注意对这些重边加以区分。求边双连通分量•边双连通分量的求法非常简单，只需在求出所有的桥以后，把桥边删除。•此时原图分成了若干个连通块，每个连通块就是一个边双连通分量。•桥不属于任何一个边双连通分量；•其余的边和每个顶点都属于且仅属于一个边双连通分量。实现proceduretarjan(xisavertex){visit[x]←truedfn[x]←low[x]←num←num+1foreachedge(x,y)fromxdoifnotvisit[y]then{tarjan(y)low[x]←min(low[x],low[y])iflow[y]dfn[x]thenmarkedge(x,y)asabridge}elseifedge(x,y)notonDFStreethenlow[x]←min(low[x],dfn[y])//thefollowingstepcanalsofindbridgesifdfn[x]=low[x]thenmarkedgeintoxonDFStreeasabridge}边双连通分量的构造•任意给定一个无向连通图，最少添加多少条边可以把它变为边双连通图？•求出所有的桥和边双连通分量，把每个双连通分量缩为一个点。•此时的图只包含缩点后的双连通分量和桥边，是一棵无根树。•统计树中度数为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求出最短路径图（所有满足DistS[u]+w(u,v)=DistS[v]的边构成的图）。•从图中去掉无用节点（把满足上面条件的边(u,v)看做有向边时不能到达T的点）。•使用经典Tarjan算法求出图中的桥，并找出所有的边双连通分量。•由最短路径图的性质，这些双连通分量可以一字排开，相邻两个之间由桥边连接。故乡的梦•对于不删除桥边的询问，最短路不变，答案就是DistS[T]。•如果删除了桥边，就离线采用以下做法求出所有此类询问的答案：•建立一个小根堆，在堆中存储一些边，边(u,v)对应的值为DistS[u]+w(u,v)+DistT[v].•依次扫描到每个双连通分量。到达一个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算法求LCAproceduretarjan(xisavertex){fa[x]←x,color[x]←1foreachedge(x,y)fromxdoifcolor[y]=0thentarjan(y),fa[y]←xforeachquery(x,y)fromxdoifcolor[y]=2thenanswerofquery(x,y)←get(y);color[x]←2;}Network•Anetworkadministratormanagesalargenetwork.ThenetworkconsistsofNcomputersandMlinksbetweenpairsofcomputers.Anypairofcomputersareconnecteddirectlyorindirectlybysuccessivelinks,sodatacanbetransformedbetweenanytwoco