Hi, everyone, welcome to this new video.
So in this video, we are going to discuss about this collision course schedule, so suppose there are
five courses labeled from zero and minus one that is labeled from zero to four.
Right.
So labeled from zero to number of courses, minus one.
So if the number of courses are five, then they are labeled from zero to four.
Now, what we need to do, we need to finish all the courses.
We need to enrol in these courses and we need to finish all the courses.
But we have some prerequisite, right.
What do I mean by requisite?
So before completing course when you need to complete course for.
So this is a prerequisite.
Similarly, before completing close to you need to complete four.
Similarly, before completing all three, you need to complete kozulin before completing, let's say
Ghostery.
You also need to complete course to right.
So this is basically when the requisite three.
So this is the requisite error rate and what we need to do.
So we need to tell whether we will be able to finish all these courses or not.
Right.
So let me try to explain again, given the number of courses, I have five courses starting from zero
to four.
Right.
So some courses are independent.
They can be enrolled in finished independently, but some courses has dependency, for example, courses
and has a dependency on course for that before the year to complete course.
For then only you can complete course.
One similarly goes to has a dependency on goals for that course for must be enrolled and completed then
only you can enroll in college to.
Similarly, Ghostery has a dependency on course.
One corsetry has also a dependency on Gosta.
So this is one to course.
One has a dependency on goals for goals too.
Has also dependency on goals for goals.
Three has a dependency on goals.
One Similarly, Corsetry has a dependency on course to also.
Right, we need to tell whether we will be able to finish all the courses or not, if we are able to
finish all the courses, we will return, true.
Else we will return false.
So for this example, can we finish all the courses?
Yes.
True.
So in what order will be able to finish the courses?
First of all, I will complete course for now after completing goals for I can complete course one and
goals to do.
I can complete course one and two and corsetry after completing one and two, we can complete corsetry
and courses zero is independent.
Right.
We started from zero to four so close to zero is independent.
So courses zero can be completed at any time.
Let's say I am completing courses at and or you can compute courses you do at the beginning or in between.
Right to consider is independent so it can be enrolled and completed any time.
So in this case, for this example, I am going to return.
True that I will be able to finish all the courses.
Right, so let's take another example.
So here.
They have provided this example, right?
So let's talk about this, so I have two courses, goals zero and goals one and goals one has a dependency
on goals zero.
So goals one has a dependency on goal zero.
So can I finish all the courses?
Yes.
First of all, I will finish goals zero.
After finishing courses zero, I can Andolan finish goals one.
So yes, through I can finish all the courses.
So that's why the output is true.
Let's talk about this case.
The number of course, is two goals zero and goals one.
So goals one has a dependency on goal zero goals.
One has a dependency on goals.
Zero net first unit to enroll and complete courses zero course zero has a dependency on goals one.
So Goals Zero has a dependency on goals, one that means you need to first complete goals.
One, then you can complete course zero.
So this is basically false, right?
We cannot complete we will not be able to finish the course because there is a cycle right courses releasing
first complete goals and then you can complete me course of anything.
First, complete goals is zero, then you can complete me.
So what do we have?
We have one cycle here.
Since we have a cycle, that means we will not be able to finish all the courses.
So that's why the output is false.
So I hope you have understood the question right now how we can solve this question.
So it's very simple, very, very simple.
But you need to do year to first figure out the A graph.
Like what I am saying is let's these are these are your dependencies to the Pentagon for that.
It three depends on too.
So what it will look like.
I have one and two.
So when the goes for two also depends on cause for right.
Two is depending upon goals for three years, depending upon two to three is depending upon two.
So tell me whether can I finish all the courses or not.
Yes, I can finish all the courses.
So true.
Now let's say I have one more prerequisite, three and four.
So three depends upon goals.
Four to three depends.
No, no.
Let's do the opposite.
For depends upon Ghostery, right, for depends upon corsetry, so for depends upon corsetry, this
is a late word for the thing for saying you can complete me only when you can complete corsetry.
So for is saying you can complete me only when you have completed corsetry corsetry saying you can complete
me only when you have completed coast to coast do you think you can complete me only when you have completed
goals for.
So this is when cycle.
Right.
This is one cycle.
So I will not be able to finish all the courses.
So that's why the output will be false.
So how are we going to solve this problem?
It's very simple.
There are two ways of solving the problem.
So first, we basically cycle detection rate, first rate cycle detection.
So given the speed accusatory, we are provided with this prerequisite.
At any rate, what we will do, we will construct the graph.
We will make this graph.
And then in this graph I will run one cycle detection algorithm.
So if the cycle is present.
So if.
Is present then, in that case, false, you cannot finish all the courses if cycle not present, if
no cycle, that means you will be able to finish all the courses.
So in that case, your answer will be true.
So after making this graph, we can run, we can write the code for cycle detection algorithm so cyclodextrin
algorithm can be implemented using the algorithm so we can write the code for cycle detection.
And if the cycle is present false, if no cycle, then true, I will be able to finish all the courses.
The second way of solving this problem is basically with the help of Topological Saad.
Right, topological.
So in topological start, if you remember, I told you that we will get an order, we will get an order
in which we need to finish because the topological sword is used in DAG directed acyclic graph.
Right.
So what do we do in logical thought?
We used to get one order in which we need to visit all the elements so topological so it can be used
here.
Right?
So either you can write the code for cycle detection or you can use topological sword.
Both of them will work.
Right.
So in topological sort, if I'm able to visit all the elements, if I am able to visit all the courses,
if I'm able to enrol in all the courses and finish them, then I will return to otherwise I will return
false.
If I'm not able to visit all the elements, all the courses, then I will return false.
So you can write the code for any one of them.
Right.
So what we will be doing, we will be writing the code for topological sort in our next video.
So this is all about this device.
I will see you in the next one.
And I highly recommend that you try to implement either one of them, either try to implement cyclic
reduction using DFS or try to write the code for topological right.
So this is all about this video.
I will see you in the next one.
Thank you.