对 Tarjan 算法的一些疑问
查看原帖
对 Tarjan 算法的一些疑问
394729
Weight_of_the_Soul楼主2022/7/31 08:46
void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    st.push(x);
    vis[x] = true;

    for(int i = lk[x]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if(vis[v])
            low[x] = min(low[x], dfn[v]);
    }

    if(dfn[x] == low[x]) {
        int y;
        do {
            y = st.top();
            st.pop();
            c[y] = x;vis[y] = false;
            if(x == y)
                break;

            a[x] += a[y];
        } while(x != y);
    }
}

如题,如果在最后的 do while 中将 if(x == y) {break;} 部分删掉就会错误,而添加后就会正确。

在下实在是太弱了想不明白,还请大佬指点迷津。

2022/7/31 08:46
加载中...