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

Question

Here is my code:- I use a map to keep track of nodes visited in current call to explore function. If some node is already visited and present in map, then i return a cycle. Also to every new call to explore from dfs function i clear map as well. It seems my code classifies come acyclic graphs as cyclic. But those inputs are huge (1000 nodes and 1000 edges) so can't debug it.

#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

Consider this graph

              1
           /   |
         /     |
        v     |
       2      | 
         \     |
          V  V
             3

It's an acyclic graph, but your implementation will classify it as cyclic. The reason is that when you start traversing, let's say from node 1, the visited and occurred data structure are in the following state,

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

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

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

In the backtracking step (3.) the node 3 is already marked as visited and sets the flag. To fix this you need to reset the occurred state of a node after you've visited all the nodes in that path.

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;
}