Cycle detection in a directed Graph

#1

right now my code gives 0 if not cyclic and 1 if cyclic, can you modify this code to get the nodes that formes the cycles?

#2

@tasfikrahman007
Will get back to you asap

#3

@tasfikrahman007
You can use a stack in this case. When you make a dfs call to a new node, insert it in the stack and also maintain the rs array because you need to check whether a certain element is in the stack or not.
When you return true at a certain point, the nodes corresponding to the cycle exist in the stack.
So you just have to print the contents of the stack at that point of time.

If my answer was able to resolve the query, please mark the doubt as resolved.

#4

thanks, I have made the changes , can you cross check it once if it is correct or not?

#5

@tasfikrahman007
Please send the updated code.

#6

here it is https://ide.codingblocks.com/s/334734

#7

@tasfikrahman007
This will definitely print the nodes which are present in the cycle but this will also print other nodes. So what I suggest it when you encounter a cycle, i.e, at the point
else if (rs[i])
{
return true;
}

you should print the values in the stack till you encounter i. This is because the edge between the current node and i is the cause of the cycle. So you print the nodes from the top of the stack till you encounter i and then return true from that point.

If you face any difficulty, please feel free to revert.