强连通分量

有向图强连通分量入门gfkd例题（POJ2186）•有一群牛，总数为N(N=10000)。•题目数据为牛之间的关系，比如说1仰慕2，2仰慕3等等，设这种仰慕是可以传递的，如果1仰慕2，那么1也会同时仰慕2仰慕的那些牛。(关系数e=50000)•如果一头牛被所有的牛都仰慕，那么它将是最受欢迎的牛。•问有多少牛是最受欢迎的。样例数据•本例数据中最受欢迎的牛为•D牛，E牛ABCDEFG怎么做？•显然，采用floyd传递闭包方法简单模拟可以解决此问题。时间复杂度o（n^3）。•枚举所有点，反向dfs深度优先遍历图。用邻接表存储边，每次搜索时间复杂度o（n+e），总复杂度o（n*（n+e））。•但是由于数据量巨大（n=10000），这两种做法超时的可能性很大。•那么有没有更好的做法呢？分析•首先让我们考虑问题的简化版本——有向图没有环路的情况，也就是说：•不存在一条仰慕路线，可以从一头牛出发，再回到该牛。即不存在牛互相仰慕的情况。S1S3S2进一步分析•如果有最受欢迎的牛存在，•为保证该牛被所有的牛都仰慕，这个有向图将是连通图，•最受欢迎的牛不会仰慕其他牛，即他的出度为零。•最受欢迎的牛被其他所有牛仰慕，即出度为零的点应有且仅有一个。结论•这让我们就将简化版问题给解决了~•首先，统计出图中出度为0的点。•如果这样的点只有一个，那么从该点出发反向dfs遍历图。如果可以遍历所有点，那么说明这个点就是题目要求的点。•时间复杂度o（n+e）不要高兴的太早•上面的结论在有环图是否适用呢？•很可惜，结论不成立。•因为大牛可以互相仰慕，所以若最受欢迎的牛与其他牛互相仰慕，这些牛都是最受欢迎的牛。这样，满足条件的点出度可能不为0，也不止有一个。•怎么办呢？•现在，强连通分量算法出场的时候到了。定义•下面给出强连通分量的定义：•有向图中,u可达v不一定意味着v可达u.相互可达则属于同一个强连通分量•StronglyConnectedComponent，简称SCC•根据定义，在上题中，一组互相仰慕的牛就构成了一个强连通分量（一个大牛）。关于缩点法•求出强连通分量有什么用呢？•我们可以将每个强连通分量看作一个内外隔绝的包裹，忽略包裹内部的冗余边，并将这个包裹同外部点的相连的边保留，将其打包压缩成一个新的点存储下来。•最后再利用这些新的点重新建图。•这就是缩点法。原图构建新图•强连通分量A,B,C压缩成点S1•强连通分量F,G压缩成点S2•强连通分量D,E压缩成点S3ABCDEFGS1S3S2发现•新图与原图有什么不同？•因为强连通分量全部被压缩成点，新图将一定是一张有向无环图。•而对有向无环图的问题结论我们之前已经得出了。新的结论•很容易得到新的结论：•利用强连通分量的缩点法构建新图，在新图中如果只有一个出度为0的点且该点与其他所有点连通，那么这个强连通分量中的所有点就是题目要求的点。•下面的问题，就是如何求强连通分量了。强连通分量算法•求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，时间复杂度均为o（n+e）。•其中Kosaraju算法要对原图和逆图都进行一次DFS，另外两种算法只要DFS一次，Gabow算法是Tarjan算法的改进。•下面简单介绍Kosaraju算法。Kosaraju算法（黑书286）•算法步骤(正确性证明略)–对有向图进行DFS，记录下顶点变黑的时间A[i]。–改变图G的每一条边的方向，生成新图GT。–按上次DFS顶点变黑的时间A[i]由大到小顺序对GT进行DFS。遍历结果构成森林W。–W中每棵树的结点构成了有向图的一个强连通分量。DFS（黑书285）•在演示之前，重新介绍DFS深度优先搜索为结点着色以表示结点的状态的过程。•每个顶点开始均为白色。•搜索中被发现时置为灰色。•结束时又被置成黑色(即当其邻接表被完全检索之后)。演示•对G进行dfs，记录下顶点变黑时间A[i]。•得到A[i]从大到小的顺序：•FGACDEBA(5)B(1)C(4)D(3)E(2)F(7)G(6)演示•改变图G的每一条边的方向，生成新图GT•按A[i]由大到小顺序FGACDEB对GT进行第二次DFS•得到森林w•FG||ACB||DEA(5)B(1)C(4)D(3)E(2)F(7)G(6)演示•根据森林w•FG||ACB||DE•由每个强连通分量为搜索树中的一棵子树。得到已拓扑有序的强连通分量•S2||S1||S3ABCDEFGS1S3S2总结•对某些题目，内部点之间的联系不会和外部点作用而影响到结果，那么强连通分量可以缩成一点，考虑为一个整体。•缩点可以简化构图（有环图变无环图），这样更容易发掘出各个强连通分量外部之间的规律。•关于缩点法的进一步深入讨论，请参考周源2005年信息学奥赛冬令营论文。部分用到强连通分量的题目•POJ2186PopularCows(基础)•POJ2553TheBottomofaGraph（alpcOJ1274）(基础)•POJ1236NetworkofSchools(基础)•2010中南赛lightsources（alpcOJ）(基础)•POJ2762Goingfromutovorfromvtou?(中等，弱连通分量)•POJ3160FatherChristmasflymouse(难，DP题)•POJ1904King‘sQuest(难，推荐，非缩点，匹配思想与强连通分量的转化)补充targantargan•任何一个强连通分量，必定是对原图的深度优先搜索树的子树。targan思想•我们首先要确定每个强连通分量的子树的根。然后从这些根出发找到强连通分量。targan•在这里我们维护两个数组，一个是A[1..n]，一个是minlink[1..n]。•A[i]表示顶点i开始访问时间。•minlink[i]为与顶点i邻接的顶点未删除顶点j的minlink[j]和minlink[i]的最小值•(minlink[i]初始化为A[i])。targan•这样，在一次深搜的回溯过程中，如果发现minlink[i]==A[i]那么，当前顶点就是一个强连通分量的根。•而当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。Tarjan_Algorithm•step1:•找一个没有被访问过的节点v，gotostep2(v)。否则，算法结束。•step2(v):•初始化indx[v]和mlik[v]•对于v所有的邻接顶点u：1)如果没有访问过，则step2(u),同时维护mlik[v]2)如果访问过，但没有删除，维护mlik[v]•如果indx[v]==mlik[v]，那么输出相应的强连通分量