Hi, everyone, welcome to this new video.
So in this video, we are going to write the code for this problem cause schedule.
And as discussed in our previous video, I'm going to write the code for topological chart.
So what is topological thought and how it works?
So all of these things we have covered in our previous videos in topological short video.
Right.
So before writing topological thought, what we should have we should have one graph.
Right.
So given this input, we need to create graph out of it.
Now, graph can be implemented via two ways at the center matrix and at the center list.
Right.
So we can implement our DNA matrix or we can use our list so we can use any one of them.
Let's say I am using list, so let's create a graph and I'm going to use a list.
So suppose this is our graph, let's say, for one, two and three.
This is my graph.
So how it will look like in addition to the list.
So these are nodes.
One, two, three.
Let's remove three, one, two.
And so one, two and four.
So what will happen?
So after one, one is pointing towards three.
So in the list of one, I will have three node three four two.
Two is also two can also reach two vertex three.
So in their list I will have three, four, four.
I can reach to either one or two, so I will have one and two and three can not reach anywhere.
So I didn't see list of three is empty.
So basically three will not be present in our DNC list.
Right.
So three will not be the only one to unfold.
Now, if it is like three is also pointing towards, let's say five and six, that in that case I will
also have three and is a list of three.
I will have five and six.
So this is the first step that we need to do.
We need to make a list out of this closet at night.
So let's start doing that.
So we need a list, so this is an order to map.
We have one map, right, map of integer and.
One last.
Let's say Grauwe.
So what I'm doing here, see, what is this, this is nothing but a map, right?
This is a map and in map waterski.
So key is basically integer.
And what is value?
Value is basically a list, that list of integers.
So key is integer and value is a list of integers.
Right.
OK, so let's create our graph for them to do for creating the graph we need to operate over this particular
today.
So I called zero.
So the name is very big.
Let's show the Tuppy.
So I called zero elastin prerequisite added size.
And I placeless, so what is a AIA's basically first element that is zeroth element and what is being.
So B.A. is basically your second element, that is the next one, right?
What is A and B. So it is a given indication that this big, etc. today is MBA.
So AA depends on being late, for example, when GOMAA four.
So when is a coffee for his buffet.
So one depends on four.
That is four in the list of four.
I will have one right like this.
So one is depending upon four.
So what we need to do graph of B I so what this graph of B one list.
Right.
So in that list I need to insert of I thought I need to insert AA.
So now my graph is ready.
Right.
My graph is ready now.
So after creating this graph, what is the next step in topological chart.
So next step is basically you need to populate in degree at a rate we need to create integrity.
So how many courses are there?
There are two, three, five courses.
So if the number is the value of no, of course it is five, then I will create an array of size five.
And initially the degree for all the elements at zero eight seven degrees zero, then we will iterate
over this graph.
So what is the degree for for so negative four for will be zero in degree of one when.
What is the degree of two again.
One.
What is it.
Degree of three.
It is two.
Right.
So we need to populate this integrity.
So for populating this in degree array what we can do, let's first create this integrity and integrity.
What will be it says it size will be the number of courses you have.
And what we need to do initially indicated for all the elements is zero.
So instead of using integer, let's use Vector here.
So Victor and degree, so how many courses are there, what would be the size of the victor number of
courses and we need to initialize with zero, so initialized with zero, right.
So what is the effect of this line?
So where this line will do this line will create this vector and it will initialize all the values to
zero.
So what is the size of the vector number of courses and what to value to initialize initialized to zero?
So all the values will be initialized to zero and that is what we want.
Now we need to fill this in degree area also.
Right.
And how we can do that.
So when you are creating your graph in this loop, only you can initialize your integrity.
So degree of AAII.
Plus plus, that is all that you need to do, right?
What I'm doing here is.
So if this is the condition I have been coming for and I have to go my food and let's I have one comadre,
so what the graph look like, one has a dependency on food.
Who also has a dependency on food and wine also has a dependency of three.
So this is AA.
Remember, this is a so whenever we encounter one, whenever we encounter one, we will increment its
integrity.
Right.
So I am encountering when two times, first time and this second time, what is the degree value and
degree value is to.
So that's why it is correct.
Right.
I am encountering to only one time so this will be only one time plus plus and is the degree of to only
one.
So that's how our integrity will be populated.
So we have our integrity, no, and not a logical standard of logical thought, but we need to do we
need to create Accu right and what else?
We need to insert all the elements, all the nodes whose integrity is zero zero means independent.
So I call zero elastin integrity darte, says I placeless.
So if any degree of aliment I is zero, that means discourse is independent.
Since discourse is independent, it must be present in the queue.
So could not push a simple.
Now, a standard topological sort part to embody, so while Geldart says.
Is greater than zero.
So while MICU is not empty, what I will do, I will pop one element, let's say Naude, that will be
good old friend.
And so after popping the element, but we need to do since we have visited one element, right.
Litzman Dana Count visited the number.
Of course I have installed and finished, so finished.
So how many courses I have finished as of now.
Zero now.
What I will do, the finished courses plus plus rate, I am taking one element out of the queue and
I am enrolling that into that course and I am finishing that course.
So I finished courses plus plus after that, what we need to do, we need to go to all each child so
each child will be we will get a list of child.
Right.
So all its children.
So how many children's graph of Naude GDP, each graph of Noad.
We will get all the children right.
So for example, let's say this is one, this is two, three and four.
So coast to coast, three and four, they have a dependency on this one.
So in Cuba, you have goals one.
Right, because for course, one in degree was zero.
Now, after that, what you are doing pop the element from the Q and in the map I have this list two,
three and four.
Wait, so pop the element finished courses plus plus I finished the course one.
Now from the graph I will give Norvan.
So if I give an order one I will get all children two, three and four.
So two, three and four added children.
Right.
So what we need to do, we need to reduce their degree by one.
So in degree of two will reduce violence or it will become zero and negative three but will reduce by
one.
So it will become zero in degree of four will be reduced by one because course one has been finished.
So degree will become a zero.
Right.
So in degree becomes zero, zero and zero.
So what we need to do, we need to trade over the children.
So let's I treat all the children.
So I will start from zero.
I lost ten children.
Dart sighs and I placeless.
What we need to do, we need to reduce the integrity of the children.
So in degree of yet child minus.
Minus right.
And if if the degree becomes zero C here the degree becomes zero.
Zero means independent.
Independent means they should be part of Q so I will insert two, three and four inside.
Q Right.
The standard topological start.
So if what we need to do, yes, we need to check.
So if the integrity of a yet child.
Becomes zero, that means this cause is independent, since this cause is now independent, this cause
should be present in our Q So push the eighth child in dequeue.
Right, and that's it.
Finally, how many courses you have finished?
You have finished these many number of courses, right?
So I have finished these many number of courses and how many courses I need to finish.
So I need to finish these courses.
No courses.
So if these two values are equal, I will return true, otherwise I will return false.
So that's it.
So let me go through the entire record once, then we will run this code.
So first of all, we are creating the graph because for topological chart, we need graph.
Similarly, for topological chart, we need to create this in the gray area, which is initialized to
zero.
Right then I am migrating over this picture today.
I am constructing the graph, I am using the list and then I am setting the integrity value rate for
all the elements.
Then I am maltreating or the integrity.
If any course is independent, then it must be present in queue.
Then finally, what we need to do.
I am calculating how many courses I have finished rate, so we need to finish these many number of course
is the name of the function is can finish.
So currently I have not finished any of the courses.
So while class size is greater than zero, while there are elements in the queue, the different elements
of the element of the queue.
And since I have completed this course, so number of finished courses plus plus then go to all the
child and reduce their in degree by one.
And if their degree becomes zero, that means that courses have now become independent.
So they should be part of.
Q Right.
So push in dequeue.
And finally, if the number of courses I have finished is equal to the number of courses I want to finish.
If these two values are equal, I will return true.
Otherwise I will return false so that that will be the complete code.
So let's try to run our code and see whether our code has some bug or it is correct.
So we have some back here, OK, compilation error.
Yeah, let's try to sum it up, Gore.
Yeah, so basically our goal is working late, so this is the entire code and as I discussed also,
so I have solved this problem using topological thought.
The other way of solving this problem is basically cycle detection algorithm.
Right.
So for cycle detection algorithm, what will do?
You have created the graph rate.
So in cyclodextrin algorithm, you also need to create one graph.
And after creating the graph, you can implement cycle detection algorithm, which is implemented using
DFS.
So you can use this algorithm.
Also our you can use topological sword, right?
So it's your choice.
You can do any of them.
So this is all about this weird device that is pretty much that I want to discuss in this video.
So if you have any doubt to ask me, I will see you in the next one.
Thank you.
Bye bye.