$tarjan$求强连通分量
思想:在$dfs$的过程中,把强连通分量中的点入栈,当找到一个强连通分量的最起始的点,就将其所在强连通分量中的点出栈。
缩点
把强连通分量中的点缩成一个点,进行重新建图,从而解决一些问题。
割点
若将这个点在图中所连的边删去,图变得不连通,则称这个点为一个割点。
考虑两种情况:
若节点$x$为根节点,则它若联结着两颗及以上数量的子树,则$x$为割点。
$otherwise$,设$x$的其中一个儿子为$v$,若出现$low[v] \ge dfn[x]$,则$x$为割点。
原文:https://www.cnblogs.com/BeyondLimits/p/11253239.html