I spent two hrs just search online try to understand this kinda problem until I saw your video. Thank you so much. U are the only one I saw that really want to explain in detail to us.
I want to thank you for the effort you've put in these videos. I've had a really bad teacher on this topic, but everything makes sense when you explain it.
old is gold here there are lot of new RU-vidrs just giving solutions for the qouestions where this guy taught the very basic algo of those solution in simplest way a long ago thank you buddy
i spent 1/3 today at work figuring out how to detect cycles in a statemachine. In the end I decided to represent the states and events (transitions) as a graph. My final solution was close to yours but I operate with one stack for explored nodes and if the the neighbor is in there i have a cycle. I think maybe your solution is better because you don't have redundand explorations (ever), but my solution might have redundant traversals. It's not significant for me because the tree only contains 6-40 nodes, but for bigger trees your solution is absolutely better! excellent video :) ty!
Thanks so much for this! I was stuck on a problem for weeks and was out of ideas. This helped me think it through from a different perspective and figure it out. I really appreciate your time and effort in putting these tutorials online.
This code is perfect example of good code quality. At the same time code make sure the system is in consistent state , most of the other youtube videos will leave the color and visited array in inconsistent state.
Awsum Explaination!! Spent hours reading the theory... BUT HERE, problems solved in minutes..... Thanks alot Tushar.. Keep posting... All the best.... !!!
Many thanks for this excellent video. It's by far the best and clearest explanation and demonstration of this problem. The theory from this helped me write in C the functions i needed for my data set. You're a star :)
Thanks very much! I leave my questions here before find out answers: 1. if there is no cycle, can I use this approach to print out the elements in topological order? How? 2. if there is a cycle, can I use this approach to print out the cycle? How? 3. if there are more than one cycle, can I use this approach to print out all cycles? How?
If we look at your other programs, they use a set called visited and sometimes a stack ( the child nodes which have been processed/explored). I feel instead of introducing new terminologies here, you could use " visited" = grey set, "explored" = black set, with one key difference which is "visited" is wiped clean each time dfs() is called. This will main continuity. And white set is of course all vertices.
If you are watching this in lockdown believe me you are one of the rarest species on the earth who are willing to acheive something in life. Many students are wasting their time in watching netflix, webseries, playing games, watching movies, ludo, chatting , etc. NITj student here :)
There is much confusion for directed and undirected graph cycle detection, the code should be same in which we check for a back edge, expect for the fact that Directed graph also detects a back edge bw only two node cycle for this we can simply check neighbour is already visited or not but for Undirected we need to check back edge which ensures there are at least three nodes in a cycle. However what Tushar is explaining here is case for multiple graphs(as in disconnected graphs given as one graph).. This video need not be for Directed G alone, it's for both Directed and Undirected G. Please point out any mistake if you find so!! Thanks Cheers
Awesome solution. After looking at solutions to this problem on Leetcode, one of the solutions that a user came up with was to use Kahn's algorithm to detect the cycle. You can also find the cycle this way too. It might take a couple more for loops than the solution that you share here though
Just return true in function if you find a back edge and return true all the back and read if function returned true keep collected parent into a collection.
Why not use an enumeration with three states like Unvisited, Visiting and Visited and add a reference of this enumeration on the graph-node object itself. Might be a little more efficient in terms of not using extra space for the three collections. Great explanation though!
But if we deleted the edge of the cycle and it was also the part of some other cycle we will never be able to give the right answer . Deleting an edge can go wrong .
this is a rather complicated solution, atleast for me. Why not just keep track of visited nodes and backtrack when we are nowwhere to go at some node? It's much easier.
