如下是 tarjan 求强连通分量的代码,其中 else 部分 low[u]=min(low[u],dfn[v]); 写成 low[u]=min(low[u],low[v]); 也可以过。请问这两种写法都正确吗?蒟蒻刚学图论 1ms,能否解释一下语句的含义?
void tarjan(int u) {
dfn[u]=low[u]=++dfn0;
st[++top]=u;
for(int v : to[u]) {
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(!num[v]) {
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]) {
num[u]=++cnt, scc[cnt].push_back(u);
while(st[top]!=u) scc[cnt].push_back(st[top]), num[st[top]]=cnt, --top;
--top;
}
}