首页 > 其他 > 详细

tarjan学习笔记

时间:2019-07-26 22:33:41      阅读:61      评论:0      收藏:0      [点我收藏+]

$tarjan$求强连通分量

思想:在$dfs$的过程中,把强连通分量中的点入栈,当找到一个强连通分量的最起始的点,就将其所在强连通分量中的点出栈。

缩点

把强连通分量中的点缩成一个点,进行重新建图,从而解决一些问题。

割点
若将这个点在图中所连的边删去,图变得不连通,则称这个点为一个割点。

考虑两种情况:

若节点$x$为根节点,则它若联结着两颗及以上数量的子树,则$x$为割点。

$otherwise$,设$x$的其中一个儿子为$v$,若出现$low[v] \ge dfn[x]$,则$x$为割点。

 

tarjan学习笔记

原文:https://www.cnblogs.com/BeyondLimits/p/11253239.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!