初学割点和桥,关于定义的疑问
  • 板块学术版
  • 楼主lzy20091001
  • 当前回复1
  • 已保存回复2
  • 发布时间2024/7/31 22:35
  • 上次更新2024/8/1 09:15:09
查看原帖
初学割点和桥,关于定义的疑问
932039
lzy20091001楼主2024/7/31 22:35

对于割点 low[x]low[x] 蓝书定义:

low[x]low[x] 表示以下结点的时间戳的最小值:

  1. xx 子树中的结点。
  2. 通过 11 条不在搜索树上的边,能够到达 xx 子树的结点。

OI Wiki 定义:

还需要另外一个数组 low,用它来存储不经过其父亲能到达的最小的时间戳。

?

有如下几个问题:

  1. 第一个条件为什么不说成 xx 自己,而要用这么别扭的说法?
  2. 是至少 11 条还是仅 11 条?
  3. 割点和割边的 low[x]low[x] 定义是否不同?为什么蓝书上是相同的?
  4. OI Wiki 的定义是什么意思?和蓝书完全不一样?
2024/7/31 22:35
加载中...