浅谈tarjan

野鸡题解

Posted by ethan-zhou on November 10, 2021

我向来玩不明白 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 最小的节点那里统计,并且可以证明这个节点是强连通分量所有节点的共同祖先)。

举一个野鸡题解的例子:


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon