void tarjan(int x)
{
vis[x]=1;
sta.push(x);
dfn[x]=low[x]=++wuy;
for(int i=0;i<vec[x].size();i++)
{
int nex=vec[x][i];
if(!dfn[nex]){
tarjan(nex);
low[x]=min(low[x],low[nex]);
} else if(vis[nex]) low[x]=min(low[x],dfn[nex]);
}
if(dfn[x]==low[x]){
jis++;
dis[jis]=a[x];
while(sta.top()!=x)
{
dis[jis]+=a[sta.top()];
b[sta.top()]=jis;
vis[sta.top()]=0;
sta.pop();
}
vis[sta.top()]=0;
b[sta.top()]=jis;
sta.pop();
}
}
中
else if(vis[nex]) low[x]=min(low[x],dfn[nex]);
的 dfn[nex]改成low[nex]也是对的,但是在割点操作中必须是dfn[nex]这两个有什么区别,或者是说为什么会这样。
目前个人理解(可能肯定有错)
low[nex]指的是这个点能到达的最老的祖先,在割点中这样操作计算机会认为当前点能到达low[nex],但是实际上有可能不可以,只能通过其他节点中转才可以到达,所以割点只能写dfn[nex],但是我不理解为什么tarjan两者都行,求解答