Tarjan算法是图论中比较重要的一个算法，它用来求得一个有向图得强连通分量(Strongly Connected Component)下用scc代称，首先介绍强连通分量是什么。
感性地去理解，就是一个有向图中每个有环子图，严谨得说，就是求子图，这样的子图满足子图上得每一个点都可以到达它上面任意一个点，特别说明一个点也是强连通分量。
如果需要直观的去观察可以去这个网站。
求得一个图的scc有什么用呢？我们可以这样理解，求scc的过程也就是在缩点，将每一个scc看成一个点，这样我们最终的到的就是一个DAG，对于DAG，我们就可以1利用它的性质去完成一些题目，Tarjan算法就是起到了这样一个转化的作用。
如何实现呢？
我们需要一个栈和一个dfn数组来维护low数组，dfn就是这个结点对应的dfs序，栈则是起到一个存放祖先，弹出同一个scc中的点的作用
放上代码
void dfs(int u) { dfn[u] = low[u] = ++cnt; st.push(u);inst[u]=1;//入栈记录 int v; for(int i=0; i<p[u].size(); i++) { v = p[u][i]; if(!dfn(v)) { dfs(v); low[u] = min(low[u],low[v]); } else if(inst[v]) low[u] = min(low[u],dfn[v]);//是dfn[v],但是写成low[v]也不会错，但是与Tarjan的定义有不符 }//维护low[u] int temp; if(low[u]==dfn[u]) { ++num;//发现一个scc while(1) { temp = st.top();st.pop();inst[temp]=0; scc[temp] = num; if(temp==u) break; }//u及它以上的所有结点弹出作为一个scc } return ; }
原文：https://www.cnblogs.com/delta-cnc/p/12709298.html