[模板]tarjan——最后通牒

这么久了我还是不会板子,你们随便笑话我吧。

再不会打我实在是无能为力了。

这篇博客写的像个智障一样。。。写它的目的就是自嘲?

才不是,为了方便查阅,因为我真的记不住。

对于割边,要存储该点入边的编号,因为更新low时不能沿着反向边爬回去。

遍历没走过的儿子时判定:如果儿子的low大于该点的dfn,则两点之间的路为割边。

对于割点,表达式为low[son]>=dfn[father].而对于根节点,必须有至少2个儿子满足条件时才能说根是割点。

从一个节点扫到的所有点都可以更新low值。

边双,就是割掉所有的割边之后图中剩下的联通分量。

缩点时把所有在同一个edcc里的合并,用割边连边即可。得到一棵树。

点双,dfs时使点入栈,在判割点时一旦满足条件,弹栈直到这个儿子弹出,再把父节点加入构成vdcc。

但是对于根节点是不是割点的判定没有变化。

缩点时,因为一个割点可能包含于多个vdcc,所以把割点作为中转站,把割点与其所在的vdcc连边,得到一棵树。

对于有向图强联通分量,也是维护了一个栈,dfs到点时加入。

搜索到在栈里的点(祖先)时更新low。如果回溯前dfn==low那么不断弹栈直到本节点弹出构成一个scc。

剩下的边会把图变为DAG,是有向无环图,接下来要拓扑排序而不是dfs!!

原文地址:https://www.cnblogs.com/hzoi-DeepinC/p/11373637.html