关于有向图 Tarjan 算法模板的一些疑问
  • 板块学术版
  • 楼主ThySecret
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/4/5 12:21
  • 上次更新2024/4/5 15:44:59
查看原帖
关于有向图 Tarjan 算法模板的一些疑问
1055410
ThySecret楼主2024/4/5 12:21

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]);
            // low[ver] = min(low[ver], low[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);
    }
}
2024/4/5 12:21
加载中...