Topological sort | Course schedule 2 | Leetcode
Vložit
- čas přidán 6. 07. 2020
- This video explains a very important programming interview concept which is based on graph algorithm and is known as topological sort.This is a very important concept for solving graph problems based on ordering.We can find the topological sort using the simple DFS along with a STACK.Topological sort for a graph is only possible if it is a directed acyclic graph (DAG).I have explained the entire algorithm by taking proper examples and have also shown the code implementation using a problem course schedule 2 which is from leetcode #210.I have shown the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOs:-
Course Schedule: • Course Schedule | Dead...
DFS: • Depth first search | D...
You teach a topic and then you solve a question based on that topic. This is the best approach of teaching. Thanks
Welcome
@@techdose4u hey i am a bit confused would you pls clear it? if we start at node 4 the order comes out to b 5 3 0 4 1 2 which is not correct i guess? would pls explain this to me i am not getting it?
@@neghatnazir1668 you are correct
@@neghatnazir1668 Try to run a loop from starting vertex to end vertex you will get the answer
@@techdose4u Even if there exists a loop, still there is the possibility to cover all the courses.
Ex. [[0,1], [2,0], [2,1], [3,1], [3,2]]. ( [0, 1], indicates that to take course 0 you have to first take course 1 )
In the above example, there exists a loop but still, we can complete all the courses in the following order : [0,2,1,3].
@techdose, you are doing great job . I used to follow nich white and Kevin naughton . Now iam waiting for your videos. Keep doing!
Thanks :)
Same for me as well
Same. @techdose completely dominates them!
Great video, thank you for clear explanation. One addition here, instead of doing double work (pushing elements to stack and popping every element to get answer), you can add each new element on front of LinkedList and then return the LinkedList.
Quick, crisp and clear!! Fantastic way of explaining Topological sorting in 13 minutes.!
Thanks
Thank you so much this channel, this channel focusses on solving all difficult problems based on advanced concepts. Love it
This video Clear all my doubts regarding topological sort, thank you sir
Thank you for great explanation..your approach to explain problems is best!
really good one keep sharing such vedios
awesome explination of topological sort algorithm
Such a good and clear explanation ! Thank you for the time you put in making this awesome video!
Welcome :)
your explanations goes smoothly in my mind, thanks for help !
Welcome :)
graph videos are a real delight. Thanks for the content
Welcome:)
Great work, man!
Great content :)
Awesome 🔥🔥🔥
Very helpful video. You explained it very well.
Doing a great work brother... Keep this spirit up... Your videos are really helpful.. 👌😊😊
in three hours ive got my last exam at my carrer as engeneer, and this helped a lot. Hopepefully ill aprove, thanks a lot
perfect explanation sir, thanks a lot , following your graph series from the beginning , please continue this as i am learning a lot from this, and graph is my biggest fear
Okay sure.
The day before yesterday I came to youtube for a solution to a question, as usual, randomly I picked your video. I don't know what happened after that day, whenever I search for the question on youtube I'm writing Techdose at the end.
Conclusion: The way you teach and make us understand every topic is too good.
Thanks 😊
brilliant explanations,love all your videos
one of the best channel for CS in youtube...thank u so much for such awesome contents... and keep helping us like this..
Sure. Thanks :)
In search this was 3rd result, I'm glad I chose this.
It was amazing ,thanks buddy :)
great video
Best in class channel with the best in class explanation. Thankyou so much.
Welcome :)
Content at its best! How much hours did you spend in making the videos bro? Efforts behind the scenes matters a lot! Usually i dont comment in any videos, but i used to comment to value your efforts 💖
good one
Thank you!!
Thanks. its good that you explain the subject using pseudo code aswell.
Welcome
Such simple and elegant explanation can only be expected on TECH DOSE🍺
😁
Quality content every time
😁
Amazing way of teaching bro, loved it..
Keep it up.
Thanks!
Thanks ☺️
Wonderfully explained as always!
Thanks agile :)
great explanation, recommending to everyone
Thanks :)
thanks a lott, explained so nicely... keep making such videos!!
Thanks
Excellent explanation sir, keep uploading more videos on graph problem.
Thanks
beautiful!
Very thorough explanation. I am always looking for your explanation before solving any Leetcode problem.
Great :)
Nice video
Best video for kahn algorithm
Thanks
This is best playlist on CZcams to learn Graphs ❤❤❤❤
Thanks ☺️
what if in starting we goes to node 3 rather than going to 2 in dfs, then answer would be changed na?
In the given example, from node 0 you first traversed to 2 then to 3 so the stack will be { 2, 1, 3, 0, ....} but if we traversed node 3 first before 2 then the stack will be { 1, 3, 2, 0, ....} as we see the stack is not in topological order. Because when we run our program in pc we don't know what node will be traversed first. Can you explain this case?
simple and clear explanation.. Great!.
Thanks
in 4:00 if I start from node 3, then the order will get messed up, right?
Amazing video.....best explanation.
Thanks
Can i also start from other vertex rather than 0?
really nice and clear
Thanks Yihong :)
What about loops in the schedule? We need to return an empty array in that case.
How could something be such easy. Thanks 😊🙏
Welcome 😊
Amazing Explanation!
Thanks
last few seconds was awesome it's more like listening to an terms and conditions for an insurance policy 🤣😄
😅 I just want to wrap the unnecessary talks quickly 😅
@@techdose4u hehehe..correct
Nice explanation. Always worth watching your videos.👍
Thanks.
😊😊😇😇☺️.. great video
Thanks
@TECH DOSE I am having one doubt, Can we write 0 before 4 in the top sort? like 5, 0, 4 likewise? Please clarify.
Thanks sir for such a great explanation, genius 🥰
Welcome :)
Your explanations and solutions are so beautiful.
Thanks
Excellent Explanation..... Please upload leetcode daily challenge questions also..Your videos were very helpful..
Thanks :)
very nicely explained !!!
Thanks
I didn't think of using the stack. What is the thought process for solving the problem? How did you come up with stack?
Very nice explanation 👍👏😊
Thanks
sir why cant we push the processed node and return answer following the exact method you taught in course schedule i. when we make a course processed=1 at that time why cant we push and add to result? Thank you in advance
buddy it is showing TLE in graph coloring ??
if its possible i need some application of topological sort in field of providing accessibility in organic areas
This approach is accepted by LC. Naturally because of the method `detectCycle`, the solution is beaten by many who got it done within 1 dfs method..But honestly, this solution should be taught first before attempting NeetCode's. This solution is way simpler to understand and implement!
Hello sir. Does it matter which edge we start with for the topological sort? Say we begin with 3, wouldn't 3 come before 2 in the stack?
No, it does not matter. 3 will come before 2 in stack but when we pop elements, it will result in coming at end in the order which is correct.
Hello sir ! can u also share the notes that u write while teaching ??
Best explanation ✨✨
Thanks :)
I solved this Course Schedule I/II QS using the concept of Detect Cycle in a Graph (Using Colour Method). If there is a cycle you will not be able to complete the courses. else you can always take all the courses.
For printing the courses, you can put into an array when you visited all its descendants.
Thanks 😊
Welcome
Super explaination sirr
Thanks
gud explanation !! Plz Make videos on Minium spanning tree kruskal & prims algo
It will eventually come. Making videos topicwise in order.
there is an extra recursive call to check cycle , we can do it using bfs in less time complexity
👍🏼
Hello! I was doing this exercise I started with 4to 2 then I went to 4to 1. I then restarted at 5 to 0 to 3 and I got the following result 5,0,3,4,1,2. Is this correct? I read that one can start with any node (not just 5 or 4). Also I saw another comment with I different topological ordering which I also got 5,0,3,4,2,1. Can anyone explain why these are wrong? I am a beginner and I am having some difficulty grasping this concept. Thank you!
I have implemented the same algo but just used the cycle detection method shown by you in the "course schedule1" problem. But its giving me a time Limit Exceeding error. Is that the reason why you slightly tweaked the cycle detention method in this problem?
I don't exactly remember the reason 😅
thanks for your work
Welcome
sir, please try to add a video for egg dropping puzzle if possible
Very well explained the logic :))
But I could not get one thing in the code-->
How are we making adjacency list??
//Make adjacency list
for(int i=0;i
U r just awesome 💕
Thanks :)
Why is the motivation to perform Khan’s algorithm/Topological Sort with a DFS approach to solve this problem while in the explanation of the topic is based of BFS? What’s the reason? Can both approaches be used to apply Topological sort?
what if we add two more edge (5 -> 6) and (6 -> 2)
@TECH DOSE Even if there exists a loop, still there is the possibility to cover all the courses.
Ex. [[0,1], [2,0], [2,1], [3,1], [3,2]]. ( [0, 1], indicates that to take course 0 you have to first take course 1 )
In the above example, there exists a loop but still, we can complete all the courses in the following order : [0,2,1,3].
There is no cycle in your graph :)
very good explanation
Thanks
Tech Dose, Awesome Explanation. Your reach would increase if you can share the solutions in java.
Yea...but I think people should focus on learning logic and implement themselves. Already codes are available in all languages.
@@techdose4u Agreed! Great, explanation, Man! Cheers!
Bhai tabiyat sahi rakho aur videos banate raho, katai aag ho aap
Bhagwan hai bhai ye
😅
Sir why did u used a graph coloring method for a detecting cycle in a directed graph, as in your vidoe you have used another approach.
Graph Coloring is simple and works in O(V+E) otherwise we will have to use stack.
Super video! I applauded for ₹200.00 👏👏👏
Thanks for supporting ❤️
@@techdose4u Thank you for the remarkable videos 😀
Welcome :)
❤
baap!
Nice video. How did you find cycles in the graph?
watch the course schedule video - it checks for cycles in the graph
In 1st video CS-I (Course schedule I) you created ajd by adj[i[0]].push_back(i[1]); i.e. 0->1 , and here inverse adj[i[1]].push_back(i[0]); 1->0. Also I checked for CS-I adj[i[1]].push_back(i[0]); is also passing, please explain. Thanks
If you are checking cycle then it doesn't matter how you take. It should be same for all the edges
@@techdose4u Thanks for this quick response and and all amazing content.
Using recursion-
bool isCyclic(vector adj[],vector& vis,vector& order,int curr){
if(vis[curr]==0){
return true;
}
if(vis[curr]==-1){
vis[curr]=0;
for(auto e:adj[curr]){
if(isCyclic(adj,vis,order,e)){
return true;
}
}
order.push_back(curr);
vis[curr]=1;
}
return false;
}
vector findOrder(int numCourses, vector& prerequisites) {
vector adj[numCourses];
vector vis(numCourses,-1);
vector order;
for(int i=0;i
Please make video on finding articulation point
It will come in connectivity topic. I am covering topicwise. Have patience.
Why is simple BFS not a solution to this problem?
Sir, can you explain how find cycle in a graph
Already explained for directed and undirected graph... Check his Graph playlist
Awesome explaination, One suggestion Topological sort explaination video should come before the Reconstruct Itinerary video. So that flow can be maintained.
Okay i will reorder. Thanks for letting us know.
Bro please explain Leetcode Island Parameter problem
1)
m a fresher, working in IT company of Jodhpur(9 hours job). If I prep DSA with c++ , 3-4 hrs each day for 3 months(leetcode) , can I gt job at Google,FB, Apple ? If not, then hw much time/months need?
2) If.i have one project in my resume, is it enuf for project round of FAANG
You can crack job at AMAZON , Microsoft with this preparation but Google and apple requires you to distinguish yourself from the rest. Your resume should show what sets you apart from the rest. This prep is done by thousands of jobseekers and hence you need either an exceptional coding profile or an exceptional dev profile or both in a balanced way.
@@techdose4u is one project enuf?
@@tech_wizard9315 nope man it wont be enough at any day for any of the product based companies
@@tech_wizard9315 one project is enough but it depends on what work you had done, the complexity and level of responsibility you were handling and the amount of effort you put. This defines your character as an SDE. Don't worry if you have 1 project, but the important thing is your dedication alongwith complexity and level of ownership of your project.
Bro , I am in a same situation 2020 batch and more from electronics batch from a tier 3 college, But I suggest you must make 2-3 Projects, OtherWise interviewer is definitely going to grill a lot. Best of luck for your preparations.
what if we get more than one components in graph and 1 component forms DAG and other does not ?
Simply , we can't do topological sort because one of component is not DAG . We will got stuck in cycle while selecting courses for that component.
@@AjayKumar-un2fz
But in such case an empty array can't be returned as output coz there must be some courses we can take as valid courses which forms different component .
Read this: stackoverflow.com/questions/36712146/if-topological-sort-uses-dfs-how-can-it-succeed-on-disconnected-graphs
After graph series, can you start with greedy
I will try.