心魔
塔扬缩点是我长时间不想学的算法了。。。并查集能解决的事绝对不用并查集！！！，然而，随着题目难度加深，我发现有些题目不得不用Tarjan解决，而且现对于并查集而言，思维量可以大大减少，所以这里写下这篇博客，算个纪念吧
Tarjan是一位非常操蛋帅的人，发明了了大量的算法，什么并查集求LCA啊，什么SPLAY啊...不过最出名的还是他发明的缩点算法了
正文
首先，什么叫缩点呢？我们需要先理解什么是强连通分量
强连通分量指的是：在一个有向图中，强联通分量的点可以互相到达，如在下图中，一块黄的就是一个强联通分量
其实我不太说的清楚原理，直接上代码注释好了：
int DFN[maxn],LOW[maxn],index;//序号及环开头的序号int S[maxn],top;//手写栈bool ins[maxn];//是否进栈int col[maxn],numc;//染色void Tarjan(int u){ DFN[u] = LOW[u] = ++index; S[++top] = u;//进栈 ins[u] = true; for(int i = head[u];i;i = E[i].nxt){ int v = E[i].v; if(!DFN[v]){ Tarjan(v); LOW[u] = min(LOW[u],LOW[v]);//找爸爸（环开头）最小的 } else if(ins[v]){ LOW[u] = min(LOW[u],DFN[v]);//判断谁是爸爸 } } if(DFN[u] == LOW[u]){//发现更新完一轮自己是爸爸 numc++; while(S[top + 1] != u){ col[S[top]] = numc;//出栈，染色 ins[S[top--]] = false; } } } 关于Tarjan缩点的技巧
我们分两种情况：
1.题目直接考Tarjan（重点）
这种情况一般是直接考缩点，通常和图论的知识连用，而又以出度和入度最为常见
首先如果原图是一个无向又环图，我们是没办法对其进行某些操作的（比如可以重复走一条路但是点权只加一次这类的），因为要重复访问，所以DFS就毫无用武之地了，这时候我们就需要又Tarjan，在跑Tarjan的时候处理环的某些性质（如点权什么的），在建新图，就可以在新图上进行dp或者遍历了。
2.题目考其他
这里不再赘述，Tarjan就是一个辅助作用，把有环图缩为无环图，就可以使用一些算法解决问题了
最近刷的Tarjan的题：