我来问一个只有蒟蒻会问的问题
查看原帖
我来问一个只有蒟蒻会问的问题
203083
炎炎龙虾楼主2020/7/22 16:03

这是一段典型的Tarjan求图的割点的一段代码(奆佬勿喷)

void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                if(x!=root || flag>1)
                    cut[x]=true;
            }
        }
        else
            low[x]=min(low[x],dfn[y]);
    }
}

为什么倒数第三行不用low[y]来更新low[x]呢?

2020/7/22 16:03
加载中...