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,所以效果一样。
但是我不理解的是,为什么这份代码不适用于求割点和桥,请求关于此类问题的详细解答。
谢谢!