Welcome back.
Let's now go ahead and code the solution which we discussed in the previous video.
Now for this let's go ahead and write the function check if can finish.
And this is going to be the implementation of the topological sort which we discussed.
Now this function is going to take in n and the prereqs.
All right.
Now inside this function let's have a stack.
So let's initialize this.
So const stack.
Now at this point it's going to be empty.
Now we will call our helper function to get the adjacency list and the indegree array for each of the
vertices.
So let's say const and we will have our helper function which will just return an array of arrays.
So one element in this array is going to be our adjacency list.
And the second element is going to be the in degree array.
All right.
So I'm just doing this together.
So that's why we have over here uh the adjacency list and in degree as two elements of this array.
So this is the way that you can return two different arrays in JavaScript right from the same function.
And this is going to be what we get back from our helper function.
And this function is going to take in n and the prereqs.
So let's go ahead and write our helper function.
So let's just have a placeholder over here.
Now I'm saying const helper is equal to function.
And this takes in n and the prereqs.
All right.
So we will come back and fill this up later.
So at this point we have got our adjacency list and the Indegree array which has the indegree factor
for each element.
Now let's just loop through the Indegree array and identify the indices or the vertices where the indegree
is zero.
And let's push that to our stack.
So we say for let I is equal to zero I less than.
Indegree dot length.
I plus plus or again in degree dot length.
Or I can just say n and I say I plus plus right now for each of these indices let's check the indicator
value.
So if that is equal to zero we will push it to our stack.
So if in degree at I if this is equal to zero then we will push it to our stack.
So we can say stack dot push.
I, which is the vertex itself.
Right.
So we are just getting all the vertices which have an indegree factor zero into our stack.
Now let's have count is equal to zero.
All right.
So we initializing a variable count.
And let's say that's equal to zero.
And we will be incrementing it whenever we take something out from our stack, and we will have a while
loop.
So let's say while stack dot length.
So as long as something is there in the stack, we will keep looping through.
And at the end of this while loop, when we come out, we're just going to check whether count is equal
to n right, which is the number of vertices.
So if count is equal to n then we will return true which means that there is no cycle.
And hence we can finish all the courses.
And if it's false, if count is not equal to n, then we did not get every vertex into the stack.
And that's because every vertex at no point, every vertex had the indegree factor equal to zero.
And that is possible when there is a cycle, right.
So let's proceed.
So inside the while loop we are going to take from the stack from the end the element.
So we are going to pop from the stack.
So let's say current is equal to stack dot pop.
But we're just taking one element which has indegree factor equal to zero.
And then we are just incrementing count.
So we say count plus plus.
All right.
Now what we will do is we will identify its neighbors and we will decrease the indegree factor of its
neighbors by one by one.
Say const neighbors is equal to adjacency list at current right.
So we get the array of its neighbors.
Now we are just going to loop through these and decrement their indegree factor by one.
So for let I is equal to zero I less than neighbors dot length I plus plus.
Now for each neighbor, let's say const neighbor.
Is equal to neighbors at I to make our code a bit cleaner.
Now for each neighbor, we will decrease their indegree factor by one so we can say indegree at neighbor
minus minus.
So we are decrementing the indegree factor by one.
Now we will check if the indegree factor has become zero.
So if indegree at neighbor.
If this is equal to zero, then we will push it to our stack so we can say stack, dot, push.
Neighbor.
All right.
So this is it.
So now we when we come out of this while loop, we will just check what is the length of the count.
So if the count is equal to n then that means that there is no cycle.
That's why every element came to the stack at some point.
So this is how we are going to implement this.
Now we just have to finish our helper function.
And the helper function is to build the adjacency list and the Indegree array together.
Now let's say const adjacency list.
Is equal to new array.
Of length n, and then let's just fill every element with zero, every position with zero.
And now we're just going to map through every position.
And we are going to change it to an empty array.
All right.
So at this point we have an array of arrays which is the adjacency list.
And every element is just an empty array.
Now let's also say const indegree.
This is also going to be a new array of length n.
And let's just fill it with zero.
So the indegree factor of every element at this point is taken as zero.
All right.
Now let's just loop through the prereqs which is given to us.
So for let prereq of prereqs.
So we take each prerequisite.
And again, remember if we have an element something like this, like one comma two, this means that
to take we have to take one.
We have to first take two.
Right.
So this means the link is like this.
So we have to first take two to take one.
So for each prereq I can say const and let's have two variables.
So I can say the first one is to take and the second variable I'm just naming it first take to make
it meaningful.
So we can say whatever we have over here.
So to take one we have to first take two or the link is from 2 to 1.
Now this is going to be equal to pre-req.
All right.
So the value at index zero is going to go to two take.
And the value at index one is going to take is is going to the variable first take.
So we're just doing it in this manner.
So it's shorter the code is shorter.
And then we are just going to push to our adjacency list the correct edge.
Right.
So in our adjacency list at first take we are going to push the value of to take.
So dot push to take.
Now why is that.
So for example over here we have one comma two.
Now the link is from 2 to 1.
So at index two we are going to add the value one.
So at index two we have an array.
So to that array we are going to push this value one.
So that is what is happening over here.
All right.
Now we also need to increment our indegree factor for to take right.
Because over here you can see that to take is one right.
And over here we have one.
Now into one there is a link right.
So we have to increment the indegree factor of to take.
So we can say indegree.
Add to take.
Plus plus.
So we are incrementing the indegree factor at to take plus by one.
Now once we are out of this for loop, we have built our adjacency list and our indegree array and we
just need to return both of these.
So that's why just we are just making them into one array where these two are the elements.
So adjacency list is the first element.
And the second element is the indegree array.
So that we can return them together.
Because there is no way that you in JavaScript you can return two things separately, right?
So we can just make both of the things into one array and return it as one array.
So over here when we call the helper function we get back this array.
And we have the first element over here at index zero we call it adjacency list.
And the indegree is passed to this indegree over here.
So this is how our function works.
Now we are done.
Now let's go ahead and test our function and see whether it's working.
Now first let's just have a simple example.
Let's say n is equal to two.
And let's say the prerequisite bits are and it's an array of arrays.
And the first element is going to be zero comma one.
And let's say the second element is one comma zero.
So there is a clear cycle.
So we should be getting false.
So let's.
Call our function.
So check if can finished and we will just pass in n and p.
And let's call our function and let's see what is it that we are getting?
We are expecting that we should get false.
Yes, we are getting false.
So yes, this is working.
Now let's try one more example four comma three, which is the link from 3 to 4.
Now the expectation is that we should get false because we can see there is a cycle over here.
Right.
So let's go ahead and let's try to run our code.
And yes we are getting false over here.
So yes our code is working.
Now let's try to take this example.
And let's walk through the code and let's try to see what's happening.