Java教程

Tarjan的一些学习心得与错误

本文主要是介绍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]);

附上这种情况的图：

图

这篇关于Tarjan的一些学习心得与错误的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航