Tarjan算法是一种由Robert·Tarjan（罗伯特·塔杨）发明的在有向图中求强连通分量的算法。

如果在一个有向图中，任意两个顶点都可以相互到达，则称这个有向图为强连通图，非强连通图的极大强连通子图称为强连通分量。

例如上图中，由点1、2、3、4构成的子图就是一个强连通分量。

首先引入两个数组dfn[]和low[]，其中dfn[i]表示点i第一次被搜索到的时间，与dfn序类似；low[i]表示在点i为根的dfs子树中，能够到达的点中dfn值的最小值。在整个算法结束后，low[]值相同的点就在同一强连通分量中。注意在初始化时low[i]=dfn[i]。

首先我们对所有dfn[i]==0的点i进行dfs，将搜到过的点压入一个栈中，如果下一个点已经在栈中，则更新low值。如果在某一个点回溯时发现这个点有dfn[x]==low[x]，说明以这个点为根的dfs树子树处于同一个强连通分量中，我们把栈顶元素弹出直到x被弹出，这些被弹出的点组成一个强连通分量。