rt,如果在 Tarjan 搜索中节点 v 已经被访问并且在栈中,使用 low[ver] = min(low[ver], dfn[j]); 和 low[ver] = min(low[ver], dfn[j]); 是否等效?
代码如下
void tarjan(int ver)
{
dfn[ver] = low[ver] = ++ timestamp;
stk[++ top] = ver, in_stk[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[ver] = min(low[ver], low[j]);
}
else if (in_stk[j])
low[ver] = min(low[ver], dfn[j]);
}
if (dfn[ver] == low[ver])
{
++ scc_cnt;
int tmp;
do {
tmp = stk[top --];
in_stk[tmp] = false;
id[tmp] = scc_cnt;
} while (tmp != ver);
}
}