在https://www.byvoid.com/zhs/blog/scc-tarjan中关于Tarjan算法的描述非常好，转述如下：
首先解释几个概念：
有向图强连通分量：在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通（strongly connected）。
如果有向图G的每两个顶点都强连通，则称G是一个强连通图。
非强连通图有向图的极大强连通子图，成为强连通分量（strongly connected components）。
下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达，{5}，{6}也分别是两个强连通分量。
求强连通分量的Tarjan算法如下
Targin算法
算法的基本思想如下，任选图中的一个点开始进行深度优先搜索，并按访问的顺序对点u进行编号，将结果存在数组index[u]中。另一个数组low，存储u或u的子树能够追溯到最早的栈中节点的次序号。对于一个边(u,v)我们可得
low(u) = MIN{ index(u), index(v), v还在栈中，此时还没有算完low(v)
low(v) ，u为v的父节点，v未被访问
}
当index[u] = low[u]时，以u为根的子树上的所有节点是一个强连通分量
算法的伪代码如下
tarjan(u) { index[u]=low[u]=++tmp // 为节点u设定次序编号和low初值,tmp从0开始 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 low[u] = min(low[u], low[v]) else if (v in Stack) // 如果节点v还在栈内 low[u] = min(low[u], index[v]) if (index[u] == low[u]) // 如果节点u是强连通分量的根 repeat v = Stack.pop // 将v退栈，为该强连通分量中一个顶点 print v until (u == v) }
算法应用举例
NODE INDEX LOW
1 0 0(未算完)
2
3 1 1(未算完)
4
5 2 2(未算完)
6 3 3(未算完)
{6}为一个强连通分量
NODE INDEX LOW
1 0 0(未算完)
2
3 1 1(未算完)
4
5 2 2
{5}为一个强连通分量
NODE INDEX LOW
1 0 0(未算完)
2
3 1 1(未算完)
4 4 0
NODE INDEX LOW
1 0 0
2 5 5
3 1 0
4 4 0
{1,2,3,4}为一个强连通分量，算法结束
算法的复杂度为
O(N+M)，边数+结点数