對酒當歌,人生幾何? 譬如朝露,去日苦多

过程我就不多说了,百度一下,一堆博客。

我参照kuangbin的板子和hdu1269学的基础。

只会敲板子是非常不开心的,所以我自己想了想过程为什么这样写,以下纯属个人理解,如果有错,欢迎指出。

1.我就想为什么在一个连通内只有一个节点dfn[i]==low[i]?

借鉴此博客理解

答:由于位于同一个连通内,所以任意两个节点可以相互到达,那么两者的low值一定会被另一个所影响(要看谁的low最小),所以不可能存在两对dfn和low的值相等。但是一个连通图内的low值不一定都相等(例如3个点,6条边,1-2,2-1,2-3,3-2,3-4,4-3,自己去试试就知道了)。

2.为什么low值要取最小的,最大的不可以吗?

答:对于一个连通图,我们很容易想到,在该连通图中有且仅有一个节点u的DFN值和low值相等。该节点一定是在深度遍历的过程中,该节点为连通图中第一个被访问过的节点,因为它的dfn值和low值最小,不会被其他节点影响。最大的话,出栈那里就不对了。

我们的一个连通图在栈中是根节点在最下面,也是最小的low,那么以这个为区分其他强连通分量具有重要意义,所以我们取最小。

3.这个连通图内所有的点一定都可以low一定可以取最小值吗?

借鉴此博客理解

答:dfs过程中只会遇到这四种边

树枝边:DFS 时经过的边,即 DFS 搜索树上的边

前向边:与 DFS 方向一致,从某个结点指向其某个子孙的边

后向边:与 DFS 方向相反,从某个结点指向其某个祖先的边

横叉边:从某个结点指向搜索树中另一子树中的某结点的边

第一种边是对各个点赋dfn和low的值的遍历

第二种边在回溯的时候会进行最小处理(min(自身,子节点))

第三种边会与祖先进行最小处理(min(自身,祖先))

第四种边不是这个强连通的边,不在这个问题考虑之内。

那么dfs后,一个强连通分量的low一定会是最小的。

易错点:

1.记录访问顺序时,++din,din++可能导致记录的深度为0,我的判断条件有误。

标签: none

添加新评论