有向图中的循环无法理解为什么它不起作用

Question

这是我的代码：- 我使用地图来跟踪在当前调用 explore 函数时访问过的节点。如果某个节点已经被访问并出现在地图中，那么我 return 一个循环。对于从 dfs 函数进行探索的每个新调用，我也清除了地图。看来我的代码将非循环图归类为循环图。但是这些输入很大（1000 个节点和 1000 个边）所以无法调试它。

#include<bits/stdc++.h>
using namespace std;

void explore(vector< vector<int> > &adj, vector<bool> &visited, int start, int &flag, map<int, bool> &occured)
{
   visited[start] = true;
   occured[start] = true;
   for(int i = 0; i < adj[start].size(); i++)
   {
       if(!visited[adj[start][i]])
       {
           explore(adj, visited, adj[start][i], flag, occured);
       }
       else if(occured[adj[start][i]])
       {
           flag = 1;
       }
   }
}

int dfs(vector< vector<int> > &adj, vector<bool> &visited)
{
    int flag = 0;
    map<int, bool> occured;
    for(int i = 0; i < adj.size(); i++)
    {    
        if(!visited[i])
        {
            occured.clear();
            explore(adj, visited, i, flag, occured);
        }
        if(flag == 1)
        {
            return flag;
        }
    }

    return 0;
}

int acyclic(vector<vector<int> > &adj) 
{
    vector<bool> visited(adj.size(), false);
    return dfs(adj, visited);
}

int main() 
{
    size_t n, m;
    std::cin >> n >> m;
    vector<vector<int> > adj(n, vector<int>());
    for (size_t i = 0; i < m; i++) 
    {
        int x, y;
        std::cin >> x >> y;
        adj[x - 1].push_back(y - 1);
    }
    std::cout << acyclic(adj);
}

Answer 1

考虑这张图

这是一个无环图，但您的实现会将其归类为循环图。原因是当你开始遍历时，假设从节点1开始，visited和occurred数据结构处于以下状态，

  1 ----> 2

 visited: [true, true, false]
 occurred: [{1: true}, {2: true}]

 1 ----> 2 --->3

visited: [true, true, true]
occurred: [{1: true}, {2: true}]

 1 ----> 3

visited: [true, true, true]
occurred: [{1: true}, {2: true}, {3: true}]

在回溯步骤 (3.) 中，节点 3 已被标记为已访问并设置标志。要解决此问题，您需要在访问该路径中的所有节点后重置节点的发生状态。

void explore(vector< vector<int> > &adj, vector<bool> &visited, int start, int &flag, map<int, bool> &occured)
{
   visited[start] = true;
   occured[start] = true;
   for(int i = 0; i < adj[start].size(); i++)
   {
       if(!visited[adj[start][i]])
       {
           explore(adj, visited, adj[start][i], flag, occured);
       }
       else if(occured[adj[start][i]])
       {
           flag = 1;
       }
   }
   occured[start] = false;
}

有向图中的循环无法理解为什么它不起作用

Cycle in Directed graph Can't understand why it does not work

c++

depth-first-search

directed-acyclic-graphs