Tarjan的一些学习心得与错误

Tarjan的一些学习心得与错误

在原始 /(Tarjan/) 的模板代码中， /(low/) 的处理一般是像下面这样：

inline void Tarjan(int u){
	dfn[u]=low[u]=++tim;
	GOGRA(e,head,u,i){
		int v=e[i].to;
		if(vis[v]==0){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]==1){
			low[u]=min(low[u],dfn[v]);
		}
	}
}

那么哪里有问题呢？

			low[u]=min(low[u],low[v]);
		}else if(vis[v]==1){
			low[u]=min(low[u],dfn[v]);
		}

这里的两个 /(/min/) 中的东西是不一样的！

上面那个，因为点 /(u/) 不可能是横跨两个环的点，所以使用 low[u]=min(low[u],low[v]);

而下面那种情况，点 /(u/) 就有可能横跨两个环，所以使用 low[u]=min(low[u],dfn[v]);

附上这种情况的图：