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