Welcome back.
Now, I have just visualized this over here, the, uh, the graph that we just now dealt with.
So let me just make some space over here.
And we have these prerequisites.
For example we have two comma zero over here which is this edge from 0 to 2.
And then we have one comma zero over here which is this one.
From one we have we are moving towards two.
Right.
So let me just take a pen.
All right.
So over here we have two comma zero.
So that's from 0 to 2.
Then we have one comma zero over here which is this one.
Right.
So that's going from 0 to 1.
And then we have two comma one.
So that is this link from 1 to 2 etc..
All right.
So this is the visualization of these prerequisites.
So this is our graph.
And at this point n is equal to five.
Now the adjacency list we will get back over here right the adjacency list and the indegree array for
this particular graph.
So it's going to look like this for index zero.
For node zero we have two vertices which are going out right.
So we have one over here and two.
So we have one comma two over here.
And for one we just have a connection towards two.
So just two over here for two we have just one outgoing connection to three.
So we have three over here for three we have four and for four we have two.
So this is the adjacency list.
And the indegree array is going to be like this for index zero.
That is for this vertex we have nothing coming in.
So it's going to have an indegree factor of zero.
For vertex one it has an indegree factor of one.
For two it has an indegree factor of three because one, two and three.
Right.
So there are three edges coming into it.
And then for three it has an indegree factor of one.
And for four it has an indegree factor of one.
So let's proceed.
So we are inside this function and we have got our adjacency list and the Indegree array.
Now we come over here and for I is equal to zero I less than five I plus plus we are going to loop through
this array over here the indegree array.
Right.
And whenever the indegree factor is zero we are going to push it to our stack.
So let's have our stack over here.
Now we see that the indegree factor is zero only for this vertex right.
So we're just going to push this to our stack.
And then we initialize count to be zero.
So count is now equal to zero.
Now we see that we our stack is not empty.
We have something in the stack.
So we come inside the while loop and then we are just going to pop from the stack.
So we take this out and we increment count over here.
Now over here, we are going to find the neighbors of the current vertex, which is zero.
So for this we make use of the adjacency list.
And adjacency list at zero gives us this array over here which is one comma two.
So for these two right.
So initially I is going to be zero.
Then I is going to take the value of one because the length over here is two.
So for I is equal to zero I less than two I plus plus.
So we come inside and we find the neighbor at index zero initially which is one.
Right.
And we are going to decrement the indegree factor for this vertex over here or for this node by one.
So that's over here.
We are going to reduce this by one.
And the indegree factor of this vertex becomes zero.
Now again I is incremented I becomes equal to one.
So we get this neighbor over here and we are going to decrement the indegree factor for node two also
right by one.
So we get the indegree factor of this to be equal to two.
Now we come out of this for loop again.
Uh we check if anything is zero.
Yes.
We got this to be zero.
That's why over here we are going to push this to our stack.
So now this node is pushed to our stack.
Now again we come out of the for loop and we come to the while loop.
We check over here if there is something in our stack.
Yes we have one in our stack.
So we pop this, we come inside and we increment our count right.
So our count now becomes equal to two.
Initially it was one right?
So initially it was zero.
Then when we came inside first it became one.
Now it's equal to two.
Now we come over here and the current node is equal to one right.
So we are going to take the neighbors of one which is just two.
Right.
So which is just two.
So we come over here and we decrement the indegree factor of this node by one.
So over here this minus one gives this equal to one.
So the indegree factor of node two is going to be now one.
And we check if we have anything zero right.
We don't have anything at this point to be equal to zero.
So we don't add anything to our stack.
And then we come out of the for loop.
And when we come over here we see that there is nothing in our stack.
Right.
So the stack is empty at this point.
So we come out and now the count is just equal to two.
But n is equal to five right.
So that's why we can be sure that there is a cycle.
That's why we did not get all the elements or all the vertices uh, to our stack.
Right.
So the stack did not get all the vertices in it.
So we can be sure that there is a cycle and hence we return false.
Right.
Because two is not equal to five and therefore we return false.
So this is how our code works.
So if the count is not equal to n then there is a cycle and we return false.
If it was equal we would have return true.
All right.
Now let's take a quick look at the space and time complexity of our solution over here.
First, let's take a look at the time complexity.
Now for this what all do take time.
So we start over here with this function.
Let's take a look at this function over here.
So over here we calculate we compute or we we get the adjacency list and the indegree right.
So let's take at this helper function over here.
What's the number of operations that we have.
Do we have to do over here.
Now over here to make this adjacency list which is empty.
We will be doing n number of operations.
Right.
Because because we have to map through this array.
And then we have to make every element an empty array.
So over here we are going to do n operations.
And then over here we are going to loop through the prerequisites.
So let's say there are p prerequisites.
So over here they are going to be p operations.
So we can say that over here to get our adjacency list and our indegree we are going to do O of n plus
p operations.
Right.
So again here also we are having an array of n elements.
So this also is going to take n operations.
So in total our helper operation helper function is going to do n plus p operations.
So let's just keep that aside.
Now let's come back to our main function which is check if can finish.
So what are the other operations that we are going to do.
Once we are over here we are again going to loop through the vertices and check the indegree for every
index.
Right.
So again this is going to be another n operations over here.
Now let's continue.
Now we come to this part over here where we have the while loop.
Now in the while loop, how many times are we going to loop through it?
Now in the worst case, if there is no cycle right.
So every element at some point is going to come into the stack.
Right?
So because if there is no cycle then finally the count has to be equal to n.
So in that case we can say that this while loop will do n operations.
And each time it comes in this for loop over here is going to go through the number of edges that particular
node has.
Right.
So if we add up all of those instances together that would be e one plus e two, etc..
Right.
So first it would be for in this case if n is equal to five let's say n is equal to five, then it would
be e zero where e zero is the number of edges from zero, then e one, then e two, etc. up to e four.
So if we add all of this up together, we will just get the number of edges right.
So we can see that over here in this while loop part, we are going to do a total of N plus E operations.
Again notice it's n plus E because whenever this E zero is going to happen in one instance right.
So this while loop is going to have n iterations.
So in each iteration we may do e zero, e one, e two, etc..
So all of this together is equal to e.
And this over here is going to do n iterations.
So when we do n iterations over here we will be having e zero plus e one plus E two etc. over here in
this for loop part.
So that's why the total of these two together is going to be n plus E operations.
Therefore, we can say that the time complexity of this solution is going to be n plus p plus n plus
e which is two n plus p plus e and two is just a constant.
So we can avoid that.
And we can say that the time complexity of this solution is of the order of n plus p plus e.
Where n is the number of vertices, e is the number of edges, and p is the number of prerequisites.
So this is the time complexity of this solution.
And what about the space complexity?
Let's take a look at the space complexity also.
Now we can see over here what are the things that take up space.
We have our stack.
Then we have our adjacency list.
We have our indegree array.
So these are the things that take up space over here.
Right now the adjacency list is going to have all the n vertices and the edges right.
So this is going to take space of the order of n plus e where n is the number of vertices and e is the
number of edges.
Now the indegree array is just going to take space of the order of n, because there are going to be
n indices inside it, right?
So the indegree factor for each vertex is going to be there inside it.
So this is going to take space of the order of n.
And in the stack we are just going to have the elements which have their indegree factor to be equal
to zero.
So in the worst case the graph is such that um there is all the all the vertices are just disconnected,
right.
So in that case all the vertices have nothing coming in.
So we could say that all of them have their indegree factor to be equal to zero.
And in that case the stack can take O of n space.
So again that's the worst case for the stack.
So we can say that among all of these the greatest is this.
So hence the space complexity of this solution is going to be of the order of n plus e.