我向来玩不明白 Tarjan，每年复习都要理解半天，再写半天，再调半天。
每年都会看到一些野鸡博客，搞得我迷惑半天，今年也是，最终还得感谢 @_Guoyh_ 帮我搞明白了。
为了避免之后继续迷惑，我打算把我迷惑的点记下来。
注意：本博客是作者自己的理解，可能也是野鸡博客，如有错误，还请指出。
代码第6行的含义
inline void tj(int p){
dfn[p]=low[p]=++dfsc;
st.push(p),instk[p]=1;
for(int nx:e[p]){
if(!dfn[nx])tj(nx),low[p]=min(low[p],low[nx]);
else if(instk[nx])low[p]=min(low[p],dfn[nx]);//第6行
}
//第8行
if(dfn[p]==low[p]){
int x;++colc;
do{
x=st.top();st.pop();
col[x]=colc;
instk[x]=0;//第14行
tot[colc]+=arr[x];
}while(x!=p);
}
}
一些博客说（其他的大多数博客都没说），这句是在判断：如果这是一条返祖边，就用终点的 dfn 来更新当前点的 low。
于是我就非常迷惑，如果 instack 是用来判断某一点是否在当前点的祖先??，那么为什么要在弹栈时（14行）清零，而不是在搜完一颗子树时（第8行）清零？
实际上，我们发现博客中的那句话是不对的。
考虑这样一张图：
显然，整个图是一个强连通分量。但是如果按博客的说法，那么因为 2 号点并不是 3 号点的祖先，所以 3->2 这条边不是返祖边，于是 3 号点的 low 无法更新，最终缩出来3号点自己竟然成了一个强连通分量。
我的理解
要理解为什么是判某点是否在栈里头，首先要理解栈的含义：
- 栈里放的是当前搜索过的，所有没有缩掉的点，这意味着他们都是可能与 p 在同一个强连通分量的节点。
- 更确切的说，栈里头的点是当前搜索过的，所有与 p 或者 p 的祖先在同一个强连通分量的点。
- 更确切的说，栈里头的点是当前搜索过的，所有能到 p 的点。
而这句话
if(instk[nx])low[p]=min(low[p],low[nx]);
则是看，如果 p 的子树，能跑到这些节点中，dfn 比自己小的节点（但是这个节点不一定是 p 的祖先），那么这个强连通分量就不应该在 p 这里统计（每个强连通分量在该分量中 dfn 最小的节点那里统计，并且可以证明这个节点是强连通分量所有节点的共同祖先）。
举一个野鸡题解的例子：
- Menci的Tarjan博客 其实这个博客上的其他东西还挺不错，尤其是线性基的
判断条件
- 强连通：
dfn[p]==low[p]，弹到p。 - 点双：
low[nx]==dfn[p]，则如果p不是搜索树的根，或者p在搜索树上有多个儿子，p为割点，弹栈直到nx（nx要保留，因为割点可能在多个点双中） - 边双：
dfn[p]==low[p]，弹到p，当前边为桥。
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: