I am trying to detect the cycle in a directed graph. Initially, I have assumed all nodes to be unvisited and have their value as -1 in vector<int>flag. Now we start from a source node and push into stack<int>s and make flag[source]=0 as it is present in stack. Now I will do the DFS traversal and push the nodes if(flag[node]==-1)& make flag[node]=0 in stack starting with that particular source that I pushed in first. if all the DFS directed links are visited I will pop the top element of the stack and mark it flag[s.top()]=1;
while pushing if we encounter a node with flag[nodes]==0, the cycle is detected and i do an increment in int final variable;`
my code works correctly but there is a little issue. for e.g for input with number of vertices and edges =3.
input edges:{1,3},{2,3},{3,2}
input format;
3 3
1 3
2 3
3 2
expected out: "Graph is cyclic"
if i take the only source as 2 then i get the correct answer, but if we have to check it considering each vertex as source so i use a for loop but now i get the wrong output Graph is not cyclic. will kindly request why my approach go wrong.
my code:
#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";
}
}
