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

[Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Evg, Jul 26 '20 at 07:20
That doesn't answer the question. I know it includes lots of constants and other things but here i m not concerned with it — , Jul 26 '20 at 07:33

score 1 · Accepted Answer · answered Jul 26 '20 at 07:45

Consider this graph

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

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

Thanku very much for investing your time in this. I understood — , Jul 27 '20 at 11:38

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

1 Answers1