So i recently came across the concept of checking whether Cycles are present in Directed graphs.
I wrote this code snippet.
#include <bits/stdc++.h>
using namespace std;
map<int, int> instack; // maps all those nodes who are currently in stack to 1
vector<int>adj[100005];
void dfs(int s) // s is source
{
instack[s]=1;
for (int i = 0; i < adj[s].size(); i++)
{
dfs(adj[s][i]);
if(instack[adj[s][i]]==1) {f=1;return;} // found a node already present in stack
}
instack[s]=0;
}
Apparently this is not correct. It failed in 2 test cases in one example question. I compared my code to other present online. The only difference i found was that they were also maintaining a set of fully visited nodes(what we call black set). I don’t think that is much needed here. But apparently my thinking is not very correct here.
Please tell why and at what case this snippet will fail