听灌多,来问个Tarjan相关问题
  • 板块灌水区
  • 楼主li_cat
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/7/22 20:49
  • 上次更新2024/7/22 21:49:38
查看原帖
听灌多,来问个Tarjan相关问题
631544
li_cat楼主2024/7/22 20:49

用Tarjan求强连通分量的时候
如果有一条边指向在栈中的节点
可以令lowu=min(lowu,lowv)low_u=min(low_u,low_v)嘛
我手动模拟了下,和lowu=min(lowu,dfnv)low_u=min(low_u,dfn_v)相比在处理横叉边的时候效果是不一样的

但似乎都是正确的,前者看起来似乎求的强连通分量更大

2024/7/22 20:49
加载中...