关于tarjan的疑问,求大佬解答
  • 板块学术版
  • 楼主Starlit_Moon
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/8 21:03
  • 上次更新2024/8/8 22:08:38
查看原帖
关于tarjan的疑问,求大佬解答
1087584
Starlit_Moon楼主2024/8/8 21:03

1.1.割点里的lowlow数组和割边里的lowlow数组定义一样吗

2.2.如果一样,那为什么割点能用其父节点的dfndfn值来更新其lowlow值,而割边就要判断这个问题

蓝书上对于lowxlow_x的定义:

取一下点的时间戳最小值:

1.$$subtree(x)中的节点

2.2.通过1条不在搜索树上的边,能够到达subtree(x)的节点subtree(x)的节点

那蓝书431页的图,不会使节点66的lowlow值变为11吗

2024/8/8 21:03
加载中...