Assume you have three nodes, 1, 2, and 3, as well as the edges 1->2, 1->3, and 2->3. In this graph, there is no cycle. If you don't utilize a recursive stack and only use a visited array, your visited array would look like this: You'd go to 1 (2 & 3 are adjacent to 1, you would call dfs on both as well). Let's say you visit node 2 first from node 1. Because of DFS, you will also visit node 3 from node 2. Your visited list so far will be [1,2,3]. After that, you'd visit node 3 because it hasn't been visited yet from 1. Now, You would think there's a cycle because your visited list already has node 3, but there isn't one. So, the stack is required for directed graphs.
@@JanardhanaRaoAnala no need of recursion stack if we just make visited array as vector type and pass it by value in parameter. they have used pass by reference therefore they have to explicitly use recursion stack otherwise recursion function take care of this if pass by value.
I believe we can use BFS (use queue) or DFS(use stack), all we care about visited nodes. In BFS we marked a node as visited once we put down all the adjacent nodes in queue. Correct me if I am wrong :)
I think rec-stack array is different from visited array, it will contain all the vertices while traversing any path from one vertex to its adjacent vertices and so on, once we reach to a vertex which does not have any adjacent vertices, we remove that vertex from rec-stack array and then traverse another path.While traversing one particular path, if we encounter a vertex which is already in that rec-stack then cycle exists. If we don't use rec-stack array then it may give correct output in directed cyclic graph , but for directed acyclic graph, it will give wrong output.
Is there a need of stack. we can even keep an array of nodes(visited[]) in whichwe will mark 1 if visited else 0.Now if we find an adjacent node 'u' while exploring node 'v' allready visited in array there is cycle else not.
The stack in this example is your array of visited nodes that you propose. It's saving the current path from the node you chose to start with. That's working too, but imagine we don't have any cycles in the graph, then you'll go through the same paths over and over again, because you forget you've already tried them. That's why you need a separate visited array that keeps track of all the visited nodes.
If you maintain a single visited array in this case. That means you are going to implement a block of code for when something is already visited. But that is going to create an infinite loop since you have no way to stop the code.
Give each node a level each time you go to the next one. When you find a cycle, check the difference between the levels of both the nodes. Keep track of this difference value for every cycle you identify in the graph. And return the maximum value.
For backedge detection, we need to keep track of nodes that are in our recursion stack which are not the same as visited nodes. We are using a list as it facilitate O(1) check to the presence of nodes in recursion stack. recStack[v] = true; // makes a node part of the stack recStack[v] = false;// removes the vertex from stack However the order is not of any importance for that matter. The code given stops on finding a single backedge.
The modification is in the input. if a and b are linked. In undirected, both will be adjacent to each other but in directed(assume a to b) only the adjacency will be from a to b and not b to a, which will be in the case of undirected.
Every single time there's c++ code in geeksforgeeks it throws best practices out of the window. Why tf are you using a c style array instead of a vector? And why that new? Your code is leaking memory lmao
Set speed to 1.5. You're welcome!
even x2 wouldn't hurt that much !!
why do so many GeeksForGeeks C++ solutions leak memory? Lazily converted from Java I suspect.
Yea that new is ridiculous. Also why do they insist on using c style array instead of vectors?
Why do we need to check visited array ? can't we just check what's in the recstack to decide the cycle ?
Please add an explanation why rec stack is required on top of the visited array. It is not obvious at all.
Assume you have three nodes, 1, 2, and 3, as well as the edges 1->2, 1->3, and 2->3. In this graph, there is no cycle. If you don't utilize a recursive stack and only use a visited array, your visited array would look like this: You'd go to 1 (2 & 3 are adjacent to 1, you would call dfs on both as well). Let's say you visit node 2 first from node 1. Because of DFS, you will also visit node 3 from node 2. Your visited list so far will be [1,2,3]. After that, you'd visit node 3 because it hasn't been visited yet from 1. Now, You would think there's a cycle because your visited list already has node 3, but there isn't one. So, the stack is required for directed graphs.
@@JanardhanaRaoAnala no need of recursion stack if we just make visited array as vector type and pass it by value in parameter. they have used pass by reference therefore they have to explicitly use recursion stack otherwise recursion function take care of this if pass by value.
How can a node be visited yet not be present in the recursion stack?
Think of a multi component case, then it'll be different
I believe we can use BFS (use queue) or DFS(use stack), all we care about visited nodes. In BFS we marked a node as visited once we put down all the adjacent nodes in queue. Correct me if I am wrong :)
Tushar Roy told it better. The stack is a DS that should not be even mentioned here.
Can't we go with the approach which we use for linked list?
Could anybody explain why we need a rec-stack besides the visited list?
I think rec-stack array is different from visited array, it will contain all the vertices while traversing any path from one vertex to its adjacent vertices and so on, once we reach to a vertex which does not have any adjacent vertices, we remove that vertex from rec-stack array and then traverse another path.While traversing one particular path, if we encounter a vertex which is already in that rec-stack then cycle exists. If we don't use rec-stack array then it may give correct output in directed cyclic graph , but for directed acyclic graph, it will give wrong output.
for acyclic graphs
Is there a need of stack. we can even keep an array of nodes(visited[]) in whichwe will mark 1 if visited else 0.Now if we find an adjacent node 'u' while exploring node 'v' allready visited in array there is cycle else not.
The stack in this example is your array of visited nodes that you propose. It's saving the current path from the node you chose to start with. That's working too, but imagine we don't have any cycles in the graph, then you'll go through the same paths over and over again, because you forget you've already tried them. That's why you need a separate visited array that keeps track of all the visited nodes.
infinite loop without visited array
If you maintain a single visited array in this case. That means you are going to implement a block of code for when something is already visited. But that is going to create an infinite loop since you have no way to stop the code.
how to check the longest cycle in given graph.?
Give each node a level each time you go to the next one. When you find a cycle, check the difference between the levels of both the nodes. Keep track of this difference value for every cycle you identify in the graph. And return the maximum value.
"Visited and in Stack right now"-----just visualize this yourself on a few graphs and you will get it
Why do we need to check visited array ? can't we just check what's in the recstack to decide the cycle ?
@@priyagupta1936 No because we need to detect the backedge ie relation with ancestor.Hence we need to check for both the recr stack and visited array
Where does 'adj' come from?
Can anyone tell if the edge from 0 to 2 can also be considered as back edge instead of 2 to 0?
How many cycles are in there in graph?
2 or 3
But, in reality the stack isn't a stack. It's a list, right? It's only saving the visited nodes, but it isn't popping them.
For backedge detection, we need to keep track of nodes that are in our recursion stack which are not the same as visited nodes.
We are using a list as it facilitate O(1) check to the presence of nodes in recursion stack.
recStack[v] = true; // makes a node part of the stack
recStack[v] = false;// removes the vertex from stack
However the order is not of any importance for that matter.
The code given stops on finding a single backedge.
Nice Explanation Lots of Love From Pakistan
Thanks Usama Ali :)
I think you are FASTIAN...!
You mean Omonoia
what is the modification you have made for undirected than directed graph
The modification is in the input.
if a and b are linked. In undirected, both will be adjacent to each other but in directed(assume a to b) only the adjacency will be from a to b and not b to a, which will be in the case of undirected.
@4:08 what if 1 does not have any other connected node except 0 , then how do you get 2 ? as you have not pushed it to stack
you delete 1 from stack, going back a step, and then explore other paths from 0, which is 2, pushing it back on the stack
volume is so low.try to keep it high
that's exactly what i was looking for, many thanks!
You just reading the code.
A better example could have been given.
This video would be very helpful if I could hear it :)
Is it possible to use queue , list or array instead of stack? what is the reason you selected stack?
because it's DFS
Thank you very much
very nice explanation .
Thank you, Amit!
Good I liked the explanation
Thank you!
Hello friends! (Indian accent)
this is wrong....
check for matrix
0 1 0 0
0 0 1 0
0 0 0 0
1 0 0 0
There is no cycle but this approach says yes there is
Thanks a lot mister :)!
Every single time there's c++ code in geeksforgeeks it throws best practices out of the window. Why tf are you using a c style array instead of a vector? And why that new? Your code is leaking memory lmao
why are speaking like someone is sleeping next to you and you can't speak loudly and have to make video too.😐
thanks!
I do not hear anything!
Remove the subtitles man. I am seeing nothing
"This video is contributed by Illuminati."
Who is Illuminati ?
Illuminati is a contributor who wishes to stay anonymous.
ua-cam.com/video/d-50h9nDugk/v-deo.html
Why don't we have a speed faster than 2x😂🤦
The guy's voice is so irritating