Tarjan算法：
这是SCC问题的第一个算法，由Tarjan于1972年提出。算法仍然借助DFS，但它并不依靠遍历顺序来把不同的SCC分离到不同的DFS树中，而是让多个SCC并存于同一个DFS树中，用某种手段把他们分开。考虑一个强分量C，设其中第一个被发现的点为x，由白路径定理，C中其他点都是x的后代。我们希望在x访问完成时立刻输出C。(注意这里是一个严格的数学描述)。这样，就可以在同一棵DFS树中区分开所有的SCC了。因此问题的关键是：如何判断一个点是否为SCC中最先被发现的点。 如图。假设我们正在判断u是否为某SCC中第一个被发现的节点。如果我们发现从u的儿子出发可以到达u的祖先w,显然u\v\w在同一个SCC中，因此u不是该SCC第一个被发现的节点。如果从v出现最多只能到u，那么u是该SCC中第一个被发现的节点（也许有同学会问，若所有子节点不能到达u本身，何以能说明u是和子树强联通的？其实由于DFS的特点，若这样的情况出现，实际上在u的子树上已经完成了一个强分量的寻找，u此时是只到它本身的“第一个”被发现节点，原书的描述是严格和归纳的）。这样，问题转化为求：一个点u最远能到达的祖先的d值。注意这里的“到达”可以通过后向边或交叉边，但是前提是只能通过栈里面的点而不是已经确定SCC编号的其他点。图中实线表示一条边，虚线表示一条或多条边。 定义low[u]为u及其后代能追溯到的最早祖先v的发现时间戳pre[v]，我们可以在计算low函数的同时完成SCC的计算，low函数的递推方法如下： 利用全局栈_sta保存当前SCC中的节点（注意栈中节点形成树而不一定是链），cnt为开发当前点u的时间戳，scnt为强分量编号器，id[]为强分量编号数组。 原始的Tarjan算法递推方式为：如果 pre[w]<pre[u]且w在栈中，则low[u]=min{pre[w],low[u]}，注意后一个限制是为了保证w不是在另一个已经发现的SCC中。下面的代码更简洁，在标记强分量后，只需要将low[w]设为最大值，表明它不再是任何点的祖先，那么w就不会被其他强分量吸收了，想想为什么。