关于tarjan系列的问题
  • 板块学术版
  • 楼主expnoi
  • 当前回复24
  • 已保存回复24
  • 发布时间2023/1/1 15:37
  • 上次更新2023/10/24 05:54:22
查看原帖
关于tarjan系列的问题
378346
expnoi楼主2023/1/1 15:37

1.老问题没搞明白(以前问过,但还是有点不理解)

我们都知道low[u]表示u走过若干条树边和最多一条非树边可到达的dfn最小的点的dfn值。

那么这个问题就是代码

根据定义,

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

然而

else if(instack[v])
{
	low[u]=min(low[u],low[v]);
}

也可以通过。

然后我进行了思考,请大佬评判一下我的思考是否正确。

根据定义,这份错误的代码的意义变成了可以经过多条非树边(请求评判这一条的正确/错误)。

然后因为求的是SCC,所以效果一样。

但是我不理解的是,为什么这份代码不适用于求割点和桥,请求关于此类问题的详细解答。

谢谢!

2023/1/1 15:37
加载中...