请求协助：将Tarjan递归割点算法转换为可正常运行的迭代版本

基础Graph类结构 #

class Graph {
protected:
    vector<vector<int>> adjList;
    int n;
};

递归版Tarjan割点算法 #

void DFSforTarjan(int u, vector<bool>& visited,
    set<int>& AP, vector<int>& disc, vector<int>& low, int& time, int parent) {

    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;
    for (int v : this->getNeighborVertex(u)) {
        if (!visited[v]) {
            children++;
            DFSforTarjan(v, visited, AP, disc, low, time, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u])
                AP.insert(u);
        }
        else if (v != parent)
            low[u] = min(low[u], disc[v]);
    }
    if (parent == -1 && children > 1)
        AP.insert(u);
}

问题迭代版代码（无法正常运行） #

void DFSforTarjan(int u, vector<bool>& visited,
    set<int>& AP, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<int>& children, int& time) {

    stack<int> st;
    st.push(u);
    
    while (!st.empty()) {
        u = st.top();
        st.pop();

        if (parent[u] != -1) {
            children[parent[u]]++;
        }
        visited[u] = true;
        disc[u] = low[u] = ++time;

        for (int v : this->getNeighborVertex(u)) {
            if (!visited[v]) {
                st.push(v);
                parent[v] = u;
                visited[v] = true;
            }
            else if (v != parent[u]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        if (parent[u] == -1 && children[u] > 1)
            AP.insert(u);

        if (parent[u] != -1 && low[u] >= disc[parent[u]])
            AP.insert(parent[u]);
    }
    for (int v : this->getNeighborVertex(u)) {
        if (v != parent[u] && visited[v]) {
            low[u] = min(low[u], low[v]);
        }
    }
}

问题分析与修正后的迭代版代码 #

你的迭代版核心问题是没模拟递归的两次访问节点逻辑：递归中首次访问节点时初始化参数，递归处理子节点；子节点处理完后回溯回来更新当前节点的low值并判断割点。你直接把节点弹出栈就完成所有操作，漏掉了回溯阶段的关键逻辑。

修正思路是用栈存储节点状态，标记该节点是首次访问还是处于回溯阶段，具体实现如下：

void DFSforTarjan(int start, vector<bool>& visited,
    set<int>& AP, vector<int>& disc, vector<int>& low, vector<int>& parent, int& time) {

    // 栈中存储<节点u, 是否已处理过其子节点>的状态对
    stack<pair<int, bool>> st;
    st.push({start, false});
    vector<int> children(this->n, 0); // 记录每个节点的子节点数量

    while (!st.empty()) {
        auto [u, isProcessed] = st.top();
        st.pop();

        if (!isProcessed) {
            // 首次访问节点，执行初始化逻辑
            if (visited[u]) continue; // 避免重复处理已访问节点
            visited[u] = true;
            disc[u] = low[u] = ++time;

            // 重新压入栈，标记为待处理回溯阶段
            st.push({u, true});

            // 逆序压入邻接节点，保证处理顺序和递归一致（不逆序也不影响正确性）
            vector<int> neighbors = this->getNeighborVertex(u);
            reverse(neighbors.begin(), neighbors.end());
            for (int v : neighbors) {
                if (!visited[v]) {
                    parent[v] = u;
                    children[u]++;
                    st.push({v, false});
                } else if (v != parent[u]) {
                    // 遇到回边，更新当前节点的low值
                    low[u] = min(low[u], disc[v]);
                }
            }
        } else {
            // 回溯阶段：处理子节点返回后的逻辑
            int p = parent[u];
            if (p != -1) {
                // 用子节点的low值更新父节点的low
                low[p] = min(low[p], low[u]);
                // 判断父节点是否为割点
                if (low[u] >= disc[p]) {
                    AP.insert(p);
                }
            }
            // 根节点单独判断：子节点数大于1则为割点
            if (p == -1 && children[u] > 1) {
                AP.insert(u);
            }
        }
    }
}

关键修正点 #

• 用pair<int, bool>标记节点状态，区分首次访问和回溯阶段，完美模拟递归的调用与返回流程。
• 首次访问时完成参数初始化，再将节点重新压栈标记为待处理，随后压入所有未访问邻接节点。
• 回溯阶段完成low值的层级更新，以及割点条件的判断。
• 根节点的割点判断放在回溯阶段，确保统计完所有子节点后再执行检查。

内容的提问来源于stack exchange，提问作者Jupit90