关于tarjan
  • 板块学术版
  • 楼主D2T1xubiaoshi
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/1/25 20:58
  • 上次更新2023/10/28 10:57:28
查看原帖
关于tarjan
390770
D2T1xubiaoshi楼主2022/1/25 20:58

tarjan中low数组的一个问题:

if(!dfn[v]){
   tarjan(v);
   low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], dfn[v]);

这里如果v是u的父亲,那么low[u]就能被dfn[v]更新。

如果求强连通分量和割点没什么问题,但在求割边的时候就有问题。

割边的判断法则是 low[v]>dfn[fa v],但如果v能被fa v更新时,则low[v]至少=dfn[fa v],就会出错。

所以在tarjan时要不要加上v==fa?continue这种话?

2022/1/25 20:58
加载中...