浅谈强连通分量与拓扑排序的应用

IOI2006国家集训队作业：解题报告浙江唐文斌浅谈强连通分量与拓扑排序的应用浙江唐文斌摘要强连通分量与拓扑排序是图论中最基础的算法之一。本文选取了两个简单但富有代表性的例子，说明这两个算法在一类图论问题中的应用。[例一]Goingfromutovorfromvtou?1给定一个有向图，问是否对于图中的任意两点u、v，总是存在u到v可达或者v到u（下文中将以ab表示a到b可达）可达。图中点数不超过1000，边数不超过6000。算法分析题目描述很简单，我们最直观的想法就是求一个传递闭包，然后对于任意两点a、b判断是否ab或者ba。然而在本题中点数多达1000，传统的求传递闭包方法Floyd是行不通的。题目中的规模很小，似乎我们可以枚举起点s，并且从s开始对图进行一次宽度优先搜索，这样我们可以在O（N*（N+M））时间内求得传递闭包。似乎这个办法可行，但事实上，在本题中虽然规模小，但是数据组数高达200组，所以这个方法也是必然超时的。我们抛开传递闭包，重新来看问题。题目中问是否对于任意两点都在至少一个方向上可达。那么如果两个点u、v，uv且vu，它们当然是符合要求的。所以我们第一个想法就是找到一个点集，该点集内所有点两两可达。由于其内部两两可达，所以我们可以将其缩成一个点，仅保留连向外界的边，并不会影响问题的本质。这个点集，就是强连通分量。所以我们的第一步操作就是：求图中所有的极大强连通分量，将每一个强连通分量缩成一个点，保留不同分量间的连边信息，得到一个新图。我们对原图进行强连通分量缩点得到新图有什么好处呢？在这个过程中，我们将一些冗余信息进行了处理，得到的新图具有一个很重要的性质：无环（拓扑有序）。因为如果有环存在，那么这些环上的点都是互相可达的，所以它们应该同属于一个极大强连通分量，将被缩成一个点。所以我们现在的问题就是对于新图——一个拓扑有序的图，判断图中是否任意两点是否在至少一个方向上可达。如果一个拓扑有序的图满足要求，那么它将拥有一些什么性质呢？我们先来看一些小规模的情况：（1）如果图只有一个点，则必然满足条件（2）如果图中包含两个点，那么必须从一个点到另一个点有边相连。不妨设为ab（显然b到a不可达）。（3）如果图中包含3个点，不妨设第三个为c。那么必须满足ca或者bc。通过上面3个情况的观察，我们大致就有了一个猜想：1PojMonthlySpecial–Jiajia&Wind’sstory,problemG(POJ2762)IOI2006国家集训队作业：解题报告浙江唐文斌[猜想]：拓扑图G若满足对于图中任意两点u、v均有uv或者vu，则必然存在一条通过所有点的链。[证明]：设图中的节点数目为n。当n=1时，图满足要求且包含长度为1的链。当n=k1时，假设n=k-1时猜想成立，即任何满足条件的图都存在一条通过所有点的链。由于图G是拓扑有序的，所以我们总可以找到一个没有入度的点x，将点x删除之后不会影响图中其它点对之间的连通性。由于图G是满足要求的，而将x删除后其它点对间的连通性并没有被影响，则在G中删除点x后得到的图G'也满足要求。由假设知，G'中存在一条长度为n-1的链，不妨设这条链的起点为v。由于图G满足要求且x没有入度，所以x必须存在一条路径到达v。若x通过点y到达v，而v是一条长度为n-1的有向链的起点，则链上的vy部分加上yv部分就形成了一个圈，与题设G是拓扑有序的矛盾。故x到v直接有边相连，那么将x连到v的这条边加入原有路径中就得到了一条长度为n的链。由归纳可知，对于任何一个满足条件的拓扑图G，均存在一条通过所有点的链。问题至此，已经基本解决了。我们只需要对当前的新图寻找是否存在通过所有点的路。这个过程只需要DFS即可解决。求极大强连通分量的复杂度为O(N+M)，判断是否存在通过所有点的路的复杂度也为O(N+M)。所以总时间复杂度也是O(N+M)。至此问题被完美的解决。[例二]Pipesinfactory2给定一个有向图G(V,E)，问最多能从G图中删去多少条边，且删了边之后图G的连通性不变。规模：点数不超过1000，边数不超过10000。注：关于题目在附录中有原题的英文描述，而原题经过抽象就是上面所提到的一个图论问题。但我认为出题者想考察的并不是这个问题，而是一个另外的类似问题的解法。如果上面提到的问题可以在多项式时间内解决，那么哈密顿回路问题可以也多项式时间内解决。试想一个有向图存在一个哈密顿回路，它的充要条件为图中任意两点都互相可达且可以删掉|E|-|V|条边且图的连通性不变。也就是说我们可以利用上述问题的解在多项式时间判定一个有向图是否存在哈密顿回路，更进一步，我们也可以利用上述问题的解构造出这条哈密顿回路。而众所周知，哈密顿回路目前仍然找不到确定性的多项式时间算法，所以上述问题也是不可解的。所以我猜测，出题者想考察的问题应该是这样的：给定一个有向图G(V,E)，我们可以改造这个图G中的连边得到新图G’，问图G’中至少要含有多少边，才能满足G’的连通性与图G一致。2InternationalOnlineProgrammingContest2006,problem2IOI2006国家集训队作业：解题报告浙江唐文斌算法分析仍然是类似于上面一题的想法，我们先来看图G中的每一个强连通分量123,,...kCCCC。对于一个强连通分量iC，我们如何对其进行改造，用最少的边得到相同的连通性呢？由于一个强连通分量内的点之间是两两可达的，所以最优的方法就是让这个分量内的点构成一个环，即使用iC条边（若iC=1，则不需要连边）。类似的，由于强连通分量内的点之间都互相可达，所以我们可以把它们压缩成一个点，仅保留于外界的连边信息，问题本质不变。我们不妨设压缩之后的新图为G0。所以现在的问题就是如何改造一个这个拓扑有序的图G0，用最少的边得到相同的连通性。由于图G0是拓扑有序的，所以我们所要做的就是删除尽量多的无效边，使得仍然保留原有的拓扑序。而一个拓扑有序的图中哪些边是没有必要的呢？如下图：图中的红色边即为无效边，我们的目标就是找到所有这种无效边并且加以删除。所谓的无效边，就是说对于现有的一条边uv，我们可以找到另一条通路不经过这条边从u到v。那么我们就有一个很直观的想法就是不断尝试删无效边，随便找一条边，看看是否能删，如果能删就将其删除。这个方法看起来有点玄乎，但其实是正确的，我们来看下面一个性质：[性质一]假设有当前有两条可以删除的边，不妨设ab和uv。我们任意删一条边，不会导致另一条边变得不能删除。证明：上述性质在普通有向图中显然是不成立的，看下面这个例子：显然上图中的两条红色边可以一起被删除。但是如果我先删了蓝色边，则两条红边都不能删了。但是请注意，我们现在面对的图并不是一般的有向图，而是一个拓扑有序的图。删了一条边ab之后导致另一条边uv不能删，意味着什么呢？由于删去ab之后使得uv不能删，而原本u到v存在着第二条通路现在不存在了，所以说ab这条边是u到v第二条通路上的一部分。因为ab可以被删除，所以IOI2006国家集训队作业：解题报告浙江唐文斌a到b也存在着另一条通路，那么两部分相接不就可以保证u到v仍然存在第二条通路了么？除非如上图所示，即uv也是a到b的另一条通路上的一部分。而这么一来，a可以到达u，u可以到达a，这就与我们的题设——图拓扑有序矛盾了。所以我们删除任何一条边，都不会影响到另一条本来可以本删除的边。有了性质一，我们就可以直接用上面提到的朴素算法求得解答。但是上面的方法依次枚举每一条边，然后检查去掉这条边是否仍然连通，时间复杂度较大，为2()OM。为了优化这个算法，我们不妨来规定一个检查边的顺序。我们将图G0进行拓扑排序。建立一个空图G’，按照逆拓扑序，每次加入一个点u和从u出发的所有有向边。然后检查当前加入的边集。对于当前一条边uv，看看是否可以将其删除，如果可以删除那就删。显然这样做仍然是2()OM的，尽管因为检查的边变少常系数有些变化，但并没有影响算法的时间复杂度。不过按照这个顺序处理，我们就可以进行一些优化。我们是按照逆拓扑序加点和边，也就是说当前G’中的两个点a、b的连通情况，不可能与尚未添加的点c有关系。所以我们可以维护一个局部的传递闭包，记录每两个点之间的连通信息。每次我们加了点u之后，判断一条边uv是否可以被删除只需要检查是否存在一个点x，满足u到x有边存在且x可以到达v。对于每一条边的检查，最多是()ON的。检查所有边之后，我们可以从u开始遍历一次，最多()ONM的时间就能得到从u出发到达其他点的连通信息了。所以总时间复杂度不超过()ONM。比上面的方法优了很多。到这里，问题已经基本解决。不过大家也可以发现，本题中不能被删的那些边与我们熟知的“桥”很类似，所以我们也许可以通过类似求桥的方法来进行求解，从而得到更优的算法。限于篇幅，这里就不再赘述。总结求有向图的强连通分量是一种非常常用的手段，在一个强连通分量内的点之间都是互相可达的，所以我们往往可以把它们看作一个点进行处理。而这样的一种变换，就把一些冗余信息压缩掉了，从而使得问题变得更加清晰明了，也更容易分析其本质。而经过压缩后的新图都是拓扑有序的，再对这个图的求拓扑顺序，就能方便地解决很多问题。附录[例一]英文原题[例一]参考程序G.Goingfromutovorfromvtou.docIOI2006国家集训队作业：解题报告浙江唐文斌[例二]英文原题[例二]参考程序p2.pdf