2

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";
    }
}
def __init__
  • 1,092
  • 6
  • 17
  • You have a very small failing example, so start debugging (even possible with pen and paper). – MrSmith42 Jul 23 '21 at 10:18
  • What algorithm is this supposed to be? – Surt Jul 23 '21 at 11:07
  • @surt sir Using either DFS, or BFS, or Topological sorting it is done. I'm trying to use DFS. will be thankful if you may help to figure out where I'm going wrong. – def __init__ Jul 23 '21 at 11:11
  • https://stackoverflow.com/questions/68307377/kahns-algorithm-vs-dfs-for-course-schedule-leetcode/68310296#68310296 – Matt Timmermans Jul 23 '21 at 11:17
  • 1
    In a DAG, just because you find two paths to a node, it doesn't mean there's a cycle. In the DFS test, you need to find an edge to an *unfinished* node, not just a visited one: https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs/58211392#58211392 – Matt Timmermans Jul 23 '21 at 11:22
  • @Matt Timmermans thank you for letting me know,but i am still unsure why my code fails – def __init__ Jul 23 '21 at 12:10

0 Answers0