序言

关于强连通分量的定义，请看我的前一篇文章强连通分量（上）：定义+Kosaraju算法。
上面这篇文章包括强连通分量的定义和K算法。接下来我将在这篇文章中讲Tarjin算法。Tarjin算法是求强连通分量中比较快的一种。

基本概念

dfn[i]：节点i的搜索次序编号，就是第几个被搜到的。
low[i]：i或者i的子树能回溯到的最早的点的编号。
这么说就能得到状态转移方程：
low[i]=min(low[i],low[j])，i是j的父亲节点。
low[i]=min(low[i],dfn[j])，i能到j且j在栈中。

算法过程

①更新dfn、low为搜索次序编号，将点k压入栈顶。
②搜索每一个k连结的点p：
如果没访问过（dfn[p]==0），则Tarjin(p)，low[k]=min(low[k],low[p])
如果访问过且在栈中，则low[k]=min(low[k],low[p])
③如果low[k]==dfn[k]，则此时栈中所有元素（包括k）都属于一个强连通分量，并把所有元素出栈。
④继续找dfn[x]==0的点进行新一轮Tarjin。

例子

图1

图2

图3

图4

请自行理解，谢谢。右边那个绿色的是栈。
从百度考过来的，请见谅。

代码

stack<int> st;
void tarjin(int k)
{
  low[k]=dfn[k]=++tot,st.push(k);//初始化（low、dfn、入栈）
  for(int i=head[k]; i; i=a[i].nxt)
    if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
    else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);//遍历所有连结的节点，求low[k]
  if(low[k]==dfn[k])
  {
    co[k]=++num;
    while(st.top()!=k) co[st.top()]=num,st.pop();
    st.pop();//别忘了出栈
  }//找到一个强连通分量并标注
}

小结

Tarjin是通过dfn和low、入栈出栈进行的一个求强连通分量的代码，通常用来缩点。时间复杂度O(n+m)，但是比K算法快了很多。
欢迎私信！！！

完结撒花！！！
别忘了点赞，关注，谢谢！！