今天介绍的这个算法叫Tarjan，也是一个很奇怪的名字，只是奇怪，它也是以一个人的名字命名的。与Kosaraju算法相比，除了名字更容易记住之外，还有一个优点就是只需要一次递归。虽然算法复杂度相同，但常数较小。它的知名度也更高，经常出现在比赛中。先提醒大家，Tarjan算法比Kosaraju算法更难理解。所以如果你看了这篇文章还不明白，建议你看一下上一篇。这两种算法的效果和复杂度是一样的。其实学一个就可以了，没必要去死。算法框架我们来思考一个问题，强连通分量分解算法的核心原理是什么？如果你看过我们之前的文章，那么这个问题应该不难回答。既然是强连通分量，就意味着分量中的每个点都可以相互连接。所以我们很容易想到，我们可以从一个点开始，找到一个循环让它回到起点。这样，途中经过的点都是强连通分量的一部分。但是这样会存在一个问题，就是要保证强连通分量中的每一个点都遍历完，不能有遗漏。我们也可以想办法解决这个问题，比如我们可以用搜索算法搜索所有可达点和所有路径。但是这样一来，我们就会遇到另外一个问题。这个问题就是强连通分量之间的连通性问题。我们来看一个例子：如果我们从上图中的1点开始，我们可以到达图中的每一个点。但是我们会发现1、2、3是一个强连通分量，4、5、6是另一个。当我们寻找1所在的强连通分量时，很有可能4、5、6这三个点也会被带进来。但问题是它们是自分量，不应该算在1.强连通分量1.梳理以上分析和思路后，我们可以发现，强连通分量分解算法的核心其实就是解决这两个问题，也就是完备性问题。完整就是没有遗漏、没有冗余、没有错误。我们想明白了核心问题之后，搭建思维框架就很容易了。接下来我们再看看算法的描述，会容易理解很多。算法详解Tarjan算法的第一个机制是时间戳，即在遍历时，对每个遍历的点都加上一个值。该值指示遍历哪个元素。这个应该很容易理解，我们只需要维护一个全局变量，让它在遍历的时候自增即可。写下Python代码给大家看一下：stamp=0stamp_dict={}defdfs(u):stamp_dict[u]=stampstamp+=1forvinGraph[u]:dfs(v)通过时间戳可以知道每个点的访问顺序，这个订单就是远期订单。例如，假设有u和v两个点，u的时间戳小于v的时间戳，那么它们之间的关系只有两种可能。第一个是ucanbeconnectedtov，也就是说从u到v的链接是可以通过的。二是u不能和v相连。这种情况下，不管v到u的反方向能不能相连，讨论也没有意义，因为他们之间一定不能相连。因此，如果我们要找到一条连通路径，我们还需要找到一条反向路径。在Kosaraju算法中，我们使用反向图来实现。在Tarjan，采用了不同的方法。因为我们已经知道了每个点的时间戳，所以我们可以利用时间戳来寻找反向路径。这是什么意思？其实很简单。我们在遍历u的时候，如果遇到一个时间戳比u小的v，说明从u到v存在反向路径，如果此时v还没有出栈，说明v是上游u，那么也就意味着存在一条从v到u的路径。这表明u和v可以相互连接。现在我们已经找到了一对相连的u和v，我们需要记录它们。但问题是我们怎么知道什么时候记录？边界在哪里？Tarjan算法设计了另一种巧妙的机制来解决这个问题。这个机制就是low机制，low[u]表示u能连接的所有点的时间戳的最小值。时间戳越小，在搜索树中的位置越高，也可以理解为搜索树中你能连接到的最高点。那么很明显，这个点就是搜索树的某个子树的根，点u的强连通分量所在。这里可能绕了点弯路，我们再看一张图：图中节点的序号就是递归遍历的时间戳，我们可以发现对于图上的每一个点，它们的低值都是1.显然，点1是搜索树中2、3、4这三个点的祖先。也就是说，这个强连通分量的遍历是从点1开始的，当点1出栈时，就说明以1位为根的子树已经遍历完了，所有可能的强连通分量也都已经遍历完了。被发现。这就带来了另一个问题。我们假设当前点是u，那么怎么知道u点是不是图中1这样的树的根呢？有什么方法可以标记吗？当然有，这样的一个属性就是他们的timestamp等于他们的low。所以我们可以用一个数组来维护找到的强连通分量，当这些可以遍历的强连通分量的根弹出栈时，清空数组。我们把上面的逻辑梳理一下就可以写出代码了：scc=[]stack=[]deftarjan(u):dfn[u],low[u]=stamp,stampstamp+=1stack.append(u)forvinGraph[u]：ifnotdfn[v]:tarjan(v)low[u]=min(low[u],low[v])elifvinstack:low[u]=min(low[u],dfn[v])ifdfn[u]==low[u]:cur=[]#栈中u之后的元素为完全强连通分量whileTrue:cur.append(stack[-1])stack.pop()ifcur[-1]==u:breakscc.append(cur)最后再看一下前面提到的经典例子：首先，我们从1点开始，深入搜索，直到6点结束。遍历到6点时，DFN[6]=4,low[6]=4，当6出栈时，满足条件，独立称6为强连通分量。同理，当5退出时，条件也满足，得到第二个强连通分量。然后我们回到节点3，节点3也可以遍历到节点4，4可以连接到节点1。由于1点已经在栈中，所以不会继续递归1点，只会更新low[4]=1，当4退出时，会再次更新3，使得low[3]=1。最后我们回到节点1，通过节点1遍历到节点2。2可以连接的4个点已经在堆栈中，并且DFN[4]>DFN[2]，所以2个点不会被更新。再次回到1点后，1点就没有其他点可以连接了，所以退出。退出的时候发现low[1]=DFN[1]，栈中剩下的4个元素都是强连通分量。至此，整个算法流程的介绍就结束了。希望大家能够喜欢今天的内容。
