old is gold here there are lot of new UA-camrs 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 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 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!
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.
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.
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.
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?
Awsum Explaination!! Spent hours reading the theory... BUT HERE, problems solved in minutes..... Thanks alot Tushar.. Keep posting... All the best.... !!!
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.
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 :)
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
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!
Tushar, I have not that much knowledge about graphs. Here I would like to ask one question : Only two sets is not enough to track of visited or unvisited vertices ? www.geeksforgeeks.org/detect-cycle-in-a-graph/ like this?
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 the best video on this topic. If anybody is reading this. You don't need to search for more!!
This is one of the best videos of explaining concepts on UA-cam, no joke.
Hope UA-cam gives a lot of money for your videos because they are priceless:D
old is gold here
there are lot of new UA-camrs 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 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 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!
for every tedious problem, i read through multiple things and final destination always turns out to be your videos. :D
strangely, this is true for me also.
I don't think this is very strange, though.
Couldn't find a better explanation on web than this one. Awesome job Tushar!
seriously man you are the only youtuber who tells the intuition. Other youtubers just dry run the code of gfg.
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.
Thank you this was useful . We can even use topological sort done by calculating in-degree to find a cycle
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.
Congrats, Roy.
What a good job. The best explanation I've seen so far!
Thanks Tushar, this by far the most clear explanation for this algorithm!!
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 was exactly what I needed. Thank you!
Too good Tushar!! Simplest solution for detecting cycle in directed graphs. 👏🏻
Great Job Tushar!!
The best explaining video I've found in the internet !
This was very helpful. Clearly explained with example, and is indeed comprehensive. Thanks @Tushar Roy!
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?
Awsum Explaination!! Spent hours reading the theory... BUT HERE, problems solved in minutes..... Thanks alot Tushar.. Keep posting... All the best.... !!!
Greetings from Peru, this video will help me a lot tomorrow in my presentation at the university
Thank you so very much!!! I finally understand the course schedule leetcode problem because of this video!!
Greatest explanation on UA-cam. Thank You very much!
you make Indians proud sir.
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.
Amazing! Thank you for your effort, clean and clear tutorial!
Your videos clear all my doubts...thank you
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 :)
Nicely explained Tushar!
thank you for this clear explanation with passing all steps with details
it was very helpful :)
very nice explanation. Thank you!
Best video
Best explanation.
Very lucid explanation Tushar!
Thank you Tushar, you are the man!
your handwriting is amazing!
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 :)
White set is not necessary. If you have the graph, just DFS from every node as long as it is not already in the black set.
The DFS approach is not discussed in code, the code accompanying the explanation is a Union Find.
Nice 👍
You, my friend, are GOD.
Still the best in 2020!!!
u r doing a great job tushar!...keep going like this...it will be a great benefit for us...! :D
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
Excellent presentation :) Loved it!!
Thanks Tushar, great explanation.
VERY CLEAR AND SIMPLE EXPLANATION :)
Awesome tutorial! Thank you so much!!!
You are borderline amazing
Sometimes I wish I was given the great compliment of being "borderline amazing". But the only thing I get called is "borderline".
@@suspiciousbird487 What are you talking about Lydia?
I like a simplified version where you use just two collections: seen, visiting
Instead of returning T/F, is there a way to return the verticies in the cycle? (such as a tuple of (4,5,6) ?
thank you Tushar, I realized. Great video.
Very good explanation. Thank you
Thanks..i try to implement this white/gray/black set for detecting the cycle and it works..
Hey Tushar, would you mind doing a video on heavy-light tree decomposition?
Great video, well explained
Yoh wow. That's so simple. Perfect tutorial
Thank you. This video is great!
Very good example and well explained
Where can I find the code for printing the path? The DFS parent map looks like it was only for illustrative purposes.
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.
Real nice video! Thank you!
thank u for the videos! 2019 fall!
Why don't your use adjacency list or matrix to represent graph ?
cheers this helped me to understand it in much simpler way.
nice explanation!! thanks.
thanks for you sharing
Excellent explanation !!
wonderful explanation
this looks very similar to using topological sorting to detect cycle, what's the difference?
Thank you so much for this video!!
Very helpful tutorial ... many thanks...The code takes in a Graph as an input , can i find the code/class for that graph ADT?
You are awesome!
Why aren’t my professors like him?
* Even though after taking our money*
you are one of the best
The time complexity will be O(N), where N is the number of nodes in the graph. Space complexity will be O(N).
Great job
Thanks for your video!
Great explanation :)
Thanks for this nice explanation. By the way what's the name of this Algorithm ?
AMAZING!
Which program are you using to display sets and graph in gui? Thanks
waah ldou
great lecture!
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!
The 2 algorithms for directed and undirected graphs seem so similar, and I cant seem to find the differences
For directed, it's only considered a neighbor if it is an outgoing edge.
sir please enable join option we want to support you . Thankyou
Tushar, I have not that much knowledge about graphs. Here I would like to ask one question : Only two sets is not enough to track of visited or unvisited vertices ?
www.geeksforgeeks.org/detect-cycle-in-a-graph/ like this?
+Tushar Roy thanks.
The OG.
haha lol he is a real OG 100%
Hello， I would like to know if it is possible to download the package .graph? Cuz some the Vertex type is not recognized .
Thanks
Umm isn't just finding visited node twice using dfs will work?
really amazing
What´s the O() complexity of this algorithm?
Can this also be used to find the largest cycle in a directed graph?
of course. just continue if you found a cycle, note all cycles and if every node is visited then you just compare the lengths between them
@@philippheller9439 can we use same algorithm for cycle in undirected graph?
Thanks a lot!
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 .
we can use kosarajus method also?
great.. thanks a lot..
Great!
can we just print the grey set to get the cycle?