使用栈与DFS遍历检测有向图环时多源遍历结果错误问题

核心错误点 #

• 全局vist数组未重置：你定义的全局vector<bool>vist(mx)在首次DFS遍历后所有访问过的节点都会被标记为true，后续其他源点启动遍历时，递归DFS会直接跳过已标记的节点，无法正常遍历路径检测环。比如第一个源点1遍历后，节点1、2、3的vist全部置为true，后续源点2、3启动DFS时得到的temp为空，自然检测不到2→3→2的环。
• 仅遍历节点的首个邻接节点：你处理栈顶节点x时，只调用了dfs(Graph[x][0], temp)，仅处理了x的第一个邻接点，完全遗漏了其他邻接节点，逻辑上无法覆盖完整的有向边路径。
• 迭代栈逻辑与递归DFS逻辑冲突：你原本的思路是用迭代栈实现三色标记（flag=-1未访问、0在栈中、1已处理）的环检测，但是中间插入递归DFS的逻辑完全打乱了标记流程，导致栈的弹出、flag的赋值逻辑和实际遍历路径不匹配。

修正思路 #

移除冗余的递归DFS和全局vist数组，直接基于迭代栈实现标准三色标记的有向环检测：

1. 全局维护统一的flag数组，不需要每个源点重新初始化，避免重复处理已经标记为1的节点
2. 遍历每个节点作为源点时，仅处理flag为-1的未访问节点
3. 处理栈顶节点时，遍历它的所有邻接节点，根据邻接节点的flag值判断是否存在环、是否需要入栈
4. 当节点的所有邻接节点都处理完成后，再将节点出栈并标记flag为1

修正后的参考代码 #

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int mx = 1e5 + 5;
vector<vector<int>> Graph(mx);

int main() {
    int num_vertex, num_edge;
    cin >> num_vertex >> num_edge;
    vector<int> flag(num_vertex + 1, -1); // -1未访问 0在遍历栈中 1已处理完成
    for (int i = 0; i < num_edge; i++) {
        int u, v;
        cin >> u >> v;
        Graph[u].push_back(v);
    }
    bool has_cycle = false;
    for (int source = 1; source <= num_vertex; source++) {
        if (flag[source] != -1) continue; // 已经处理过的节点跳过
        stack<int> s;
        s.push(source);
        flag[source] = 0;
        while (!s.empty() && !has_cycle) {
            int cur = s.top();
            bool all_processed = true;
            for (int neighbor : Graph[cur]) {
                if (flag[neighbor] == -1) {
                    all_processed = false;
                    flag[neighbor] = 0;
                    s.push(neighbor);
                    break; // 先处理该邻接节点，后续再回来处理剩余邻接
                } else if (flag[neighbor] == 0) {
                    has_cycle = true;
                    break;
                }
            }
            if (all_processed) {
                // 所有邻接节点处理完成，弹出当前节点
                s.pop();
                flag[cur] = 1;
            }
        }
        if (has_cycle) break;
    }
    if (has_cycle) {
        cout << "Graph is cyclic" << endl;
    } else {
        cout << "Graph is not cyclic" << endl;
    }
    return 0;
}

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