c++ - 使用堆栈和 DFS 遍历检测有向图中的循环

Question

我正在尝试在有向图中检测循环。最初，我假设所有节点都未被访问，并且具有它们的值，如-1现在vector<int>flag.我们从源节点开始，并在堆栈中存在时推入stack<int>s并生成。flag[source]=0现在我将执行 DFS 遍历并从我首先推入的特定源开始推送节点if(flag[node]==-1)并进入堆栈。flag[node]=0如果访问了所有 DFS 定向链接，我将弹出堆栈的顶部元素并标记它flag[s.top()]=1；在推送时，如果我们遇到带有 的节点flag[nodes]==0，则检测到循环并且我在变量中进行增量int final；`

我的代码工作正常，但有一个小问题。例如用于输入number of vertices and edges =3。

input edges:{1,3},{2,3},{3,2}

输入格式；

3 3
1 3
2 3
3 2

expected out: "Graph is cyclic" 

如果我将唯一的源设为 2，那么我会得到正确的答案，但如果我们必须将每个顶点视为源来检查它，所以我使用 for 循环但现在我得到错误的输出Graph is not cyclic。请询问为什么我的方法出错了。

我的代码：

#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
int mx=1e5+5;
vector<bool>vist(mx);
vector<vector<int>>Graph(mx);
void dfs(int node,vector<int>&dfs_vec){
    vist[node]=true;
    dfs_vec.push_back(node);
    for(int neigh: Graph[node]){
        if(!vist[neigh]){
            dfs(neigh,dfs_vec);
        }
    }
}
int main(){
    int num_vertex;int num_edge;
    cin>>num_vertex>>num_edge;
    int u,v;
    for(int i=0;i<num_edge;i++){
        cin>>u>>v;
        Graph[u].push_back(v);
    }
    int final=0;
    for(int source=1;source<=num_vertex;source++){
    vector<int>flag(num_vertex+1,-1);
    stack<int>s;
    s.push(source);
    flag[source]=0;
    while(!s.empty()){
        int x=s.top();
        vector<int>temp;
        dfs(Graph[x][0],temp);
        for(auto y:temp){
            if(flag[y]==-1){
                s.push(y);
                flag[y]=0;
            }
            else if(flag[y]==0){
                final++;
            }
        }
        flag[s.top()]=1;
        s.pop();

    }
    flag.clear();
    while(!s.empty()){
        s.pop();
    }
    }
    if(final>0){
        std::cout<<" Graph is cyclic";
    }
    else{
        std::cout<<" Graph is not cyclic";
    }
} 

标签： c++algorithmdata-structuresgraphdepth-first-search