萌新刚学tarjan
  • 板块学术版
  • 楼主BYR_KKK
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/26 13:22
  • 上次更新2023/11/2 18:02:58
查看原帖
萌新刚学tarjan
802664
BYR_KKK楼主2023/9/26 13:22

lowu定义为以下结点的dfn的最小值:Subtreeu中的结点;从Subtreeu通过一条不在搜索树上的边能到达的结点。\textit{low}_u 定义为以下结点的 \textit{dfn} 的最小值:\textit{Subtree}_u 中的结点;从 \textit{Subtree}_u 通过一条不在搜索树上的边能到达的结点。

OI-Wiki上这句定义是不是有问题,比如:

对于 5,6,7{5,6,7} 这个强连通分量,由 55 到 22 的过程中满足 OI-Wki 的定义,但不能认为 low5=2low_5=2 。(22 不在栈中)

2023/9/26 13:22
加载中...