G-24. Course Schedule I and II | Pre-requisite Tasks | Topological Sort
ฝัง
- เผยแพร่เมื่อ 16 ก.ย. 2024
- GfG-Problem Link1: bit.ly/3ApDfOm
GfG-Problem Link2: bit.ly/3SYjQvp
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
Understood.
Small clarification if im right.
In the first example the for GFG prerequisites its said for [1,0] '0' needs to be done before '1'. i.e 0 should come before 1.
As explained in your earlier video from defination of topological sort
for a pair [u,v] u should appear before v.
i .e to complete 'v' we need to do 'u' first.
So now why it worked in prerequisite?
because we just needed to detect the cycle..
So, why you changed the order in course schedule?
Because here we needed the output too.
On swaping them we now created the actual graph for topological sort.
in question its given [v,u]
we created [u,v] by defination of topological sort. we can create a sorted list where u will appear before v.
In actual code for Course schedule should work for both.
And in prerequisite to define as per question's defination we should also swap the pairs.
Bhaiya I have doubt that can we do this question by finding topological ordering of given sequence by dfs technique
I Have tried using dfs technique but I'm getting wrong answer so could you plz help me to solve by this technique
below is the code that I have tried
class Solution {
public:
void dfs(int Node,int vis[],vector adj[],stack&s){
vis[Node]=1;
for(auto &Adjnode: adj[Node]){
if(!vis[Adjnode]){
dfs(Adjnode,vis,adj,s);
}
}
s.push(Node);
}
bool isPossible(int V, vector& p) {
vector adj[V];
for(int i =0;i
i have tried this using dfs but it was not working can you give the proper code in dfs sir
For everyone confused on the ordering part, IN BOTH CASES, we need to create edge from 2ND TO 1ST as we need to go through 2nd to get to first , i.e. 1 -> 0.
However even if we create reverse edges, it works on the first problem since it doesnt have to do anything with the order of tasks, it just needs the count.
STILL,
THE CORRECT WAY IS : 2ND -> 1ST
You are right, I was also confused on same.
Technically you can create the edges whichever way you want, just in one solution, you will have to return the order of topo sort. No need to memorize it, just draw out and see which way your code returns the answer and if it needs to reverse. Use your intuition
So u are saying int adj[n];
for(auto vec: prerequisite){
int u=vec[0];
int v=vec[1];
adj[v].push_back(u);
@@SohailKhan-cx9gb yep
All those who are thinking that why creating reverse or opposite direction edges work for 1st question but not for 2nd.
(By opposite direction edges i mean that for a dependency of 0 on 1 i created directed edge from 0->1 instead of 1->0 in adjacency list.)
I tried to solve the question without watching the video, coincidently also did the same thing(made opposite direction edges while creating adjacency list) as striver did in prerequisites task question(1st question) and it worked but when i tried to submit the 2nd question using the same opposite direction adjacency list it gave wrong ans.
Now see dependency order in both questions is same(i.e in both the questions to pick task 0 you have to first finish tasks 1, which is expressed as a pair: [0, 1] )
but some how for 1st question creating adjacency list of reverse/opposite direction works because in first question we just need to check whether there is any cyclic dependency in courses or not. So even if we create reverse direction edges for the graph, cycle would still exist so that's why its giving correct ans.
But for 2nd question if we create opposite direction edges in graph(i.e. opposite dependency) our topological sort would also be created in reverse order of what it should actually should be and that's why it does n't work for 2nd question. It can work even if we create opposite direction edges but then we would need to reverse our topological sort array just before returning it.
Hope this will help
dude thankyou
gotcha!
Thank you so much.. I was literally looking for this comment
Well clarified ..!
yup
Just after understanding topological sort from you, I was able to solve this problem without explanations thanks!!!🙇
Meee tooooo!!!!!!
Your way of teaching is my biggest inspiration,the gem of youtube!!
Understood.
But in the first example the for GFG prerequisites its said for [1,0] '0' needs to be done before '1'. i.e 0 should come before 1.
As explained in your earlier video from defination of topological sort
for a pair [u,v] u should appear before v.
i .e to complete 'v' we need to do 'u' first.
So now why it worked in prerequisite?
because we just needed to detect the cycle..
So, why he changed the order in course schedule?
Because here we needed the output too.
On swaping them we now created the actual graph for topological sort.
in question its given [v,u]
we created [u,v] by defination of topological sort. we can create a sorted list where u will appear before v.
In actual code for Course schedule should work for both.
And in prerequisite to define as per question's defination we should also swap the pairs.
loving this series ....truly appreciate your hardwork striver ... your graph series is best ...really the best of all . keep the hard work ... after completing the graph ..i will start with your dp series.
I think in this question, if the ordering was asked then, it would lead to a wrong output, as we are reversing the edges instead of doing 0 -> 1 we are doing 1 -> 0 (example-1 prerequisite task) which would give us the ordering of 3 2 1 0 instead of 0 1 2 3 which is the correct ordering if you look at the example 1 as we have to complete 0 task inorder to accomplish task 1 and then once accomplished task 1 we can do task 2 and so on..
you need to do 2 things.
1. check if your answer array has same size of numCourses or not.
2. reverse the array and then return.
if(ans.size()!=numCourses) return vector {};
reverse(ans.begin(),ans.end());
return ans;
use the above code while returning, this is working in LEETCODE.
valid doubt but... I guess striver missed a point here he reversed the making of adjacency list ..it was not because it was reversed in question it was because we have to take tasks which can be done before hand..firstly, so if 0 can be done only if 1 is done ..our graph will look like 1-->0 ultimately giving right order
course schedule 1 :
bool canFinish(int numCourses, vector& prerequisites) {
//we have to check only for the cycyle in the directed graph .
//if cycle is present return false;
//if cycle is not present return true;
//we use topological sort to check the ordering of the course :
//first we create the inorder degree vector
vector in(numCourses,0);
for(int i=0 ;i
I came up with same solution as well lol!!
while forming the graph shouldn't we take adj[it.second].push_back(it.first) as the second one is the one which should come first
ideally you should, but it doesn't really matters in this question as answer will be the same in both cases
@@ronitkhatri3660 no, it won't give you the same answer. The vector would be reversed.
true bro @chetan
@@bhargavreddy5938 what he meant by the same answer is , at the end we have to just check the size if it is equal or not. so the ordering wont really matter there. but ya the point is correct that dj[it.second].push_back(it.first) should be done.
Bro this is because we are making a directed graph. We would have pushed the second one if it was undirected 🙂
Uploading Video at 2:30 AM Man You are the Best
He is not in India but still he is really hardworking
did this without watching video, this is wonderful
I think in the second example (where he was telling about the case which has a dependency) he went the other way around.
Understood striver you are such a gem ❤❤
Understood! Such a wonderful explanation as always, thank you very much!! (I was surprised about the number of test cases (10124) though :-)
Its just a UI fascination, nothing like that many.
@take U forward In Prerequisite Tasks It is written that for example to do task 0 you have to first complete task 1, which is expressed as a pair: [0, 1] that means there is a direct edge from 1 to 0 not 0 to 1 correct me if I am wrong bhaiya.
yeah he explained it wrong in starting
Yeah that's true
we can also use vector vec(v) also instead of array of vectors adj and yes it won't take any extra space
There are many ways for topological sort, you are using kahn's algo which is dfs+cycle detection. There is another easier dfs method of topo sort using stack but that doesn't detect cycles.
In the GFG question
To do task 0 you have to first complete task 1 and the pair is: [0, 1]
But, Striver you are saying
To do task 1 you have to first complete task 2 and the pair is: [2, 1]
Now both the explanation is opposite in the first question itself how the code run successfully? I didn't get this
Somehow it works for the first question😂😂
It could be done either way, as both will lead to cycle dependency only. I hope u got the point. 0-->1--->2--->0 OR 0--->2---->1----->0, it's one and the same thing. Both will result in a cycle.
I tried to solve the question without watching the video, coincidently did the same thing(made opposite direction edges while creating adjacency list) as striver did in prerequisites task question(1st question) and it worked but when i tried to submit the 2nd question using the same opposite direction adjacency list it gave wrong ans.
Now see dependency order in both questions is same(i.e in both the questions to pick task 0 you have to first finish tasks 1, which is expressed as a pair: [0, 1] )
but some how for 1st question creating adjacency list of reverse/opposite direction works because in first question we just need to check whether there is any cyclic dependency in courses or not. So even if we create reverse direction edges for the graph, cycle would still exist so that's why its giving correct ans.
But for 2nd question if we create opposite direction edges in graph(i.e. opposite dependency) our topological sort would also be created in reverse order of what it should actually should be and that's why it does n't work for 2nd question. It can work even if we create opposite direction edges but then we would need to reverse our topological sort array just before returning it.
Hope this will help
@@namankaushik8186 Thanks I had the same doubt
@@namankaushik8186 Thanks this solved my doubt.Good explanation
Understood topo sort so well that did both questions before even opening the solutions
Understood Sir, Thank you very much
Thankyou so much for this series!!
In this question, instead of creating topo array, we can store count and compare with V.
UNDERSTOOD..............Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Bhaiyaa, thank you so much for graph series, per bhaiya please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na bhaiya ek series please
thanks brother for helping us with such amazing lectures.
understood!
*something before something* => topoSort
Hat's off to your dedication🙏
Understood sir thankyou 🙇♂🙏❤
Course Schedule ll dfs
class Solution {
public:
bool dfs(int node,vectoradj[],vector&vis,vector&pathvis,vector&ans){
vis[node]=1;
pathvis[node]=1;
for(int it:adj[node]){
if(!vis[it]){
if(dfs(it,adj,vis,pathvis,ans)){
return true;
}
}
else if(pathvis[it]==1){
return true;
}
}
ans.push_back(node);
pathvis[node]=0;
return false;
}
vector findOrder(int numCourses, vector& pre) {
vectoradj[numCourses];
for(int i=0;i
did this on my own thanks striver
Raj sir I think you must read problem carefully because in question statement pair is given in reverse order and you explained problem in reverse manner so please try to read carefully thanks I hope you got it..
Best explanation....
Understood. Great Explanation. Topo sort is very useful ..
understood, thanks for the great video
loved the intuition!!!!tysm
Understood bhaiya
Doneeee ALONEEE!! THANKK YOUUUU STRIVERRRRR!!!!
Hare Krishna..! understood
Understood sir! 🙏🏻
Thank you! 😊🙏🏻
why do they not detect a cycle using topo sort while mentioning recruiting criteria for candidate in terms of years of experience. get experience from job , do job to have experience, have experience in prev job to get recruited . no node has inorder 0 in this and is a directed graph
Understood!
Thank you sir 🙏
Understood, all clear bhaiya
Thank you, Striver 🙂
For peeps getting confused while creating graph, Yes you all are right.
But somehow the cycle is formed in either way, but what i think is you all should do it in a right way.
So use graph[it.second].push_back(it.first) instead (on gfg). BOTH METHODS WORKS FINE
//LEETCODERS -
graph[it[0]].push_back(it[1]);
graph[it[1]].push_back(it[0]);
#Striver rocks 🤟👍
Understood
Bhai I think you are explaining in reverse order
For [1,0] You need to do task 0 to do task 1
Thanks... Understood
Thank you, the best explanation
Understood thank you so much.
Understood striver 😊
Keep bringing DSA things brother, only you and you can make career of Tier 3,4,6,7,8,9..100 students into a product based company. Your journey is so inspiring and as a boy coming from the same background as you, I relate to you very much bhai. It is so amazing to see every video of yours. The way you teach DSA, no one can teach it better than you. I had never aimed for Product Based companies but still I see all your videos. Your energy is so positive man. You have made this DSA thing look so easy. Haan kabhi kabhi thoda controversy kar dete ho, but Striver toh Striver hai bhai. Keep delivering such premium content at no premium fees bro. Be this non greedy Striver forever, who knowingly/unknowingly is helping lakhs of financially unstable men/women in pursuing their dream. Lots of Love bro.🤍
understood!
you're saying opposite, for [1,0] if 1 is to be done then firstly 0 is to be done as in the question statement.
But youre saying for [1, 0], 1 first then 0.
Hi, thanks for the video. I didn't understand the part where you said if topo.size() == N, then there is no loop. Can you shed some more light on this.
understood
actually in prerequisite prob statement say pair is given as (v
UNDERSTOOD!!!!!!!!!!
great
superb explanation
Great Explanation
Really well explained.
just loving it
Great explanation 👍
amazing
In both questions, there is given [0, 1]
Understood!!1
In leetcode Course Schedule problem, the approach using dfs for cycle detection is giving TLE. Following is my code:
class Solution {
public:
bool dfs(vector adj, vector &vis, vector &pathvis, int x)
{
vis[x]=1;
pathvis[x]=1;
for(auto it: adj[x])
{
if(vis[it]==-1)
{
if (dfs(adj,vis,pathvis,it)==true)
return true;
}
else if(pathvis[it]==1)
return true;
}
pathvis[x]=0;
return false;
}
bool canFinish(int numCourses, vector& prerequisites) {
int n = numCourses,i;
for(i=0;i
Understood :) Thank you
Thank you bhaiya
Understood 🙌. Website pr notes/code avaiable karra do please
Soon.
Why topological sort using DFS algorithm gave incorrect answer for this question
Understood❤
UNDERSTOOD
Understood💯💯
understood bhayiyaa jii
Thanks ❤️
Thankyou!!!
Understood!!!!
Great!
maja aa gya
this was amaziing ,:-)
I'm not able to understand how he creates adjacency list in many of the questions. Could anyone please brief me a bit?
Like in the first question here we have to do the 2nd task first in order to do the 1st task, so I'm not able to figure this out!
some people have explained this this in the comments
you have to see all the comments they are very helpfull
I dont understand the last condition in Prerequesite Tasks 1 problem which was return true if topo.size() == N else return false
same here! did you get it?
"understood"
love you yr, thankss you sooooooooo much, when i will get job i want meet you, to say thanks, love uuuuuuuuuuuuuu, thanks you sooo muchhhhhhhhhhhhhhhhhhhh🤩🤩
Understood:)
did it on my own.voila
\
I tried using DFS to solve, not happening. Why?
Understood :) !!
the dfs solution doesn't work for the second part of the ques when 1->2 and 2->1. the topo stack isn't detecting the cycle because both 1 and 2 will get into the stack. how should i correct it?
I agree. I implemented using dfs as well. We can't do it the way we have done for Kahn's algo.
Here's my code for the same using dfs.
In TS, the parent node is always visited before the child node. If the given graph contains a cycle, then there is atleast one edge for which parent node is NOT visited before the child node.
So, after obtaining the topological order of the Di graph, we can iterate through all the edges in the adj list and for every directed edge, we check if the position of the parent node is before the position of the child node in the topological order vector. If this condition breaks for any node, then there is a cycle present.
For performing the TS, we always visit all the adjacent vertices of a node before pushing the current node to the stack. So, all the child nodes are pushed first and then parent node is pushed into the stack. When the stack elements are popped, this order is reversed and we get the parent nodes first followed by the child nodes.
Until the stack is empty, all the nodes are added to a topOrder vector that assigns the order for every node using order counter. Finally, we iterate through all the edges in the adj list for every node and if, for any node the parent node is visited after the child node, there is a cycle present in the graph.
class Solution {
public:
void topSort(int i, vector& visited, stack& revTopOrder,
vector& adj){
visited[i] = true;
for(int v: adj[i])
if(!visited[v])
topSort(v, visited, revTopOrder, adj);
revTopOrder.push(i);
}
bool canFinish(int numCourses, vector& prerequisites) {
vector visited(numCourses);
vector adj(numCourses);
stack revTopOrder;
vector topOrder(numCourses);
int order = 0;
for(auto course: prerequisites)
adj[course[1]].push_back(course[0]);
for(int i=0; i
@@harshitpandey7521 thank you so much for the detailed explanation
understood ❤
How to implement Course Schedule II using DFS as we use the stack push only , eg: [ [0,1],[1,0] ] , the stack would be 0 1 but ans should be empty stack at last.
By taking the inPath array we used to take in detect a cycle in directed graph using DFS, here is the code for the same.
class Solution {
public:
bool hasCycle;
void topoDfsCycle(int u, unordered_map &adj, vector &vis, vector &inRecursion, stack &st){
vis[u]=true;
inRecursion[u]=true;
// pehele mere baccho ko daalo stack mein
for(int &v: adj[u]){
if(!vis[v]){
topoDfsCycle(v, adj, vis, inRecursion, st);
}
else if(inRecursion[v]){ // it is already visited and also in current recursion
hasCycle = true; // mark that there is cycle
return; // No need to further make calls
}
}
inRecursion[u]=false; // unmark // cycle bhi check kr rhe
st.push(u); // fr mujhe daalo stack mein // topological sort bhi sath m nikal rhe
}
vector findOrder(int numCourses, vector& prerequisites) {
unordered_map adj;
vector vis(numCourses, false);
vector inRecursion(numCourses, false);
// Make graph and form indegree array
for(auto &vec: prerequisites){
int a = vec[0];
int b = vec[1];
// b--->a
adj[b].push_back(a); // Directed graph
}
stack st;
for(int i=0; i
thanks bro
Hey one doubt, This question is not only based on cycle detection, We should check for bidirectional edges as well ?
if we do topo sort using dfs and then check for cycle it is giving wrong answer . I don't know why
i have a doubt , can i just simply put order in stack using topo sort by dfs and then return true if stk size equal to number of nodes or i must have to use khans algo for this ?
If you use DFS to find topo-sort, that would give the wrong answer. Since we run an outer loop (to cover all the graph components), the stack would eventually contain all 'n' elements in it. So DFS topo-sort won't work.
@@abhijeetgautam587 thnks man
@@abhijeetgautam587 It will by making few changes of detect a cycle in directed graph using DFS
@@guptashashwat can you share your solution?
idk why but using dfs topo sort does not work in these questions
why is the adjacency list reversed in second question, problem statement is same in both i.e. 0->1....can someone explain please??
adjacency list is reversed because the pair itself is given in reverse order.in second question {0,1}
represents 1--->0 as 1 need to be finished before 0.
he mistakenly explains first question in reverse manner.
understood 😀😀
pls do bit manipulation series