Tarjan的low究竟是什么意思
  • 板块学术版
  • 楼主Pecco
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/2/10 00:06
  • 上次更新2023/11/5 03:27:42
查看原帖
Tarjan的low究竟是什么意思
70304
Pecco楼主2021/2/10 00:06

很多人说定义是不经过父节点能到达的节点的最小时间戳,这个说法很不准确啊,比如这张图:

以1为根dfs的话,算出来low[4]=2,但是显然4号点是可以不经过父节点(不管dfs生成树中的父节点是3还是5)到达1号点的。

是不是只能像OI-WIKI那样定义成子树节点、及子树节点经过一条非树边能到达的所有节点中的最小时间戳?这样基本相当于按照转移方程定义了。

2021/2/10 00:06
加载中...