浅谈tarjan
source link: https://blog-e.tk/2021/11/10/%E6%B5%85%E8%B0%88tarjan/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
我向来玩不明白 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 的祖先在同一个强连通分量的点。
if(instk[nx])low[p]=min(low[p],low[nx]);
则是看，如果 p 的子树，能跑到这些节点中，dfn 比自己小的节点（但是这个节点不一定是 p 的祖先），那么这个强连通分量就不应该在 p 这里统计（每个强连通分量在该分量中 dfn 最小的节点那里统计，并且可以证明这个节点是强连通分量所有节点的共同祖先）。
举一个野鸡题解的例子：
- Menci的Tarjan博客 其实这个博客上的其他东西还挺不错，尤其是线性基的
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量 2
v1.4.4
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK