Welcome back.
In this video, let's try to think how we can solve this question in a better manner.
Now for this we will make use of the topo sort or topological sort.
Now before we see how we can use this to solve this question with which we are dealing, let's first
try to understand what is topological sort.
Now topological sort is a linear ordering of vertices.
So it's a linear ordering of vertices such that for every directed edge a to b, a appears before b
in the ordering.
So this is the definition of topological sort.
Now let's take an example to understand this.
So over here we have a graph.
All right so it's a directed graph.
Now an example of a topological sort for this particular graph would be 134265.
Again remember this is just one possible topological sort.
For the same graph we can have multiple topological sorts.
Now let's try to read this definition again.
So it's a linear ordering.
So this is a linear ordering of the vertices.
So these are the vertices in this graph.
And then it's mentioned that for every directed edge a to b a appears before b in the ordering.
Now let's take a few examples.
So over here we have a directed edge from 1 to 2.
Right now let's take a look at one and two in our ordering.
And you can see that one appears before two.
Right.
And that is what is mentioned over here a has to appear before B.
Let's take another example for example 4 to 5.
So if we look at this you can see four is appearing before five in this linear ordering.
So this is what we mean with topological sort.
Now let's also try to understand what is the criteria.
If topological sort can be applied for a particular graph.
So there is a restriction.
Now this type of a sort can be applied for a graph only if the graph is a Dag.
And Dag stands for directed acyclic graph.
All right.
So it should be a directed graph because only then we have something like A to B.
And then it should be acyclic in nature.
Now let's try to understand why it should be acyclic.
For example we have this graph over here which is cyclic in nature.
Right.
We have one going to two, two going to three and three going to one.
Now we cannot order it in a linear manner such that A appears before B, because we don't know whether
one appears before two or whether uh two appears before one.
Right.
For example, let's just write it as one, two, three.
Now, if I write it like this, you can see one is appearing before three, right?
But again over here you can see we have three, two, one.
So we could say that three should appear before one.
All right.
Now if I write it as three one, two then three is appearing before one.
And we have three appearing before two.
But then over here you have two appearing before three.
So this also cannot be done right.
Now over here, we cannot say what comes before what.
So that's why we cannot write it as a linear ordering of the pairs such that A appears before b.
Now what do I mean with that?
Let's write the possibilities right.
We have one, two and three.
So there is an edge from 1 to 2.
So I could write one, two, three.
Now we'll see why this cannot be done.
Now let's try 231.
So that's another possibility.
231.
And another possibility is 312.
Right.
312.
Now I cannot write three, two, one because there is no connection over here, right?
Similarly, I cannot write two, one, three or anything else.
So these are the three possibilities, right?
So if I start at one I can write one, two, three I could write 231 or I can write 312.
Now let's take a look at why this is wrong.
123 is it right.
So we have a link from 1 to 2.
So one is appearing before two we have a link from 2 to 3.
So two is appearing before three.
But then we have a link from 3 to 1.
So three should be appearing before one.
So this is wrong right.
So this this this is not satisfying this condition.
What about 231.
So we have a link from 2 to 3.
So this is fine.
We have a link from 3 to 1.
So this is fine.
But then we have a link from 1 to 2.
So one should come before two.
So this is also wrong.
Similarly over here we have three one and one two which is fine.
But then we have two three.
So two should be appearing before three.
So this is also wrong.
So that's why if the graph is cyclic in nature then we cannot write a topological sort for that particular
graph.
So this is an interesting observation.
So we can have the topological sort only for a directed acyclic graph.
All right.
Now let's proceed.
And let's try to think how we can use this topological sort.
Let's let's see two things.
Actually let's try to see how we can do the do a topological sort.
And let's also see how we can use it for our question.
So these are the two things that we are trying to think about now.
So again we have our example over here.
Now first let's see how we do a topological sort.
Now for this we will calculate the indegree factor for every node.
Now for every vertex.
So what is the indegree factor.
The indegree factor for a particular vertex is the number of edges pointing into that particular vertex.
For example, for this vertex over here, there is no edge pointing into it, right?
So we can say that the indegree factor for this node over here is equal to zero.
All right.
Now what about this node over here you can see there are two edges pointing into it.
Right.
So we can say that the indegree factor for this is equal to two.
Similarly for three the indegree factor is equal to zero.
For six we have one edge pointing into it.
So the indegree factor is equal to one.
For five we have three edges pointing into it.
So the indegree factor is equal to three, and for four we have one edge pointing into it.
So the indegree factor is equal to one.
All right.
Now after finding the indegree factor for every vertex.
And again we are dealing with how we can implement the topological sort.
So first we find the indegree factor for the vertices.
Then we will just take any vertex with indegree equal to zero.
Now over here for example we take vertex one.
So vertex one has an indegree factor equal to zero.
And then we disregard this vertex.
So that means that for every connection from it right.
So there is a connection from 1 to 4 and from 1 to 2.
So for these two because we have removed this we have to decrement the indegree factor by one.
So one minus one we get zero over here and two minus one we get one over here.
So the indegree factor over here is now one.
And over here is equal to zero.
Now we again take another vertex with indegree factor equal to zero.
So we can see that this node four has an integrity factor zero.
So let's take this out and we remove it.
All right.
So we consider this is removed.
So that means we are going to decrement its connections by one.
So this is having a connection from 4 to 5.
So there is an edge pointing into five from four.
So we are going to decrement the indegree factor of five by one.
And we get two over here.
All right.
Now again we continue.
We take another vertex with indegree factor zero.
So we can see that three has an indegree factor zero.
So let's take it out and we decrement these three by one.
So over here we get zero.
We get zero over here and we get one over here.
Now again we take another vertex with indegree factor zero.
So we could take any one among these two.
So let's go ahead and take two.
And this is removed.
Now there is nothing to reduce right.
So there is no edge which is proceeding out of vertex two to any other vertex.
Right.
So there is nothing to reduce.
Again we go ahead and take out six.
And at this point we reduce the indegree factor of this vertex over here.
And this also becomes zero.
And then we go ahead and take this out.
So 143265 is one possible topological sort of this graph which was given to us.
So again this is how we go ahead and implement the topological sort.
Now let's try to see whether this is valid.
For example we have this connection from 1 to 2.
And you can see that one is appearing before two which is the definition of the proper sort or topological
sort.
So yes, this is a valid topological sort.
So this is true for any connection.
For example you take the connection from 6 to 5.
So you have six before five or you have 4 to 5 and you have four before five, etc..
All right.
So we have seen how to implement the topological sort.
Now let's try to think about how we can tweak this and use this to solve our question.
Now if the graph which is given to us, if we implement the topological sort on that graph, then once
we do that, if we can check whether every vertex was reached and if every vertex was reached, for
example, in this case we got every vertex over here.
Right?
That means that the graph over here is acyclic or it does not have a cycle.
Again, in the question, we are actually checking whether the graph which is given to us has a cycle
or not.
So that is what we are checking.
Now let's take another example and let's try to understand why this helps.
So over here we have another example where there is a cycle.
So there is a cycle over here right now again let's find the indegree factor.
So over here it's 021 and one.
So nothing comes in over here.
So it's zero.
And again you have one and two two edges coming into this vertex.
So that's why the indegree factor over here is two.
And then you have one edge coming into this edge this vertex.
So the indegree factor over here is one.
And then again because this edge is coming into this vertex.
So the indegree factor over here is also equal to one.
Now let's take out let's proceed with the same method that we discussed over here.
We take out this because only this has an indegree factor.
So we take this out and we decrement this by one.
So we have the integral factor over here also one.
And we can see in all these places the integral factor now is equal to one.
And there is nothing with zero right.
So we cannot proceed and we cannot take it out.
Right.
So you can see that once we implement proper sort on this graph, we are not getting all the vertexes
right.
We just got one vertex and we are not getting all the vertices.
And that is because we were not able to proceed, because at this point there is nothing with Indegree
equal to zero.
And this is because of this cycle.
So how do we use the topo sort algorithm to solve this question?
We are going to implement the topo sort on the graph which is given to us.
And after doing that, if there is no cycle, then we would have reached all the vertices.
And if there is a cycle, then the count of vertices that we are reaching is not going to be equal to
the number of vertices.
So this is how we are going to solve this question.
And now let's try to think about how to implement this.
So again we have our graph over here.
We have already discussed the intuition and the method by which we will implement this.
Now let's go ahead and write and think about the pseudocode for this implementation of this algorithm.
So first this graph is given to us.
And for this graph we are given n.
In this case n is going to be equal to six.
And then we will be given the prerequisites array.
All right.
Now using n and the prerequisites array we will just loop through the prerequisites array.
And then we will create our adjacency list.
So this is going to be our first step.
And then we will also find the indegree factor for every node.
Right.
So again we will use the prerequisites array for that.
So if this is the graph which is given to us, the actual input for the question would be this array
over here.
Right.
So we have four comma one which means that before doing four we have to complete one which is this link
over here.
Similarly two comma one indicates before doing two we have to do one.
Two comma three indicates.
Before doing two we have to do three, etc..
So this array over here can be visualized like this.
Now we can just calculate the adjacency list and the indegree factor using the prerequisites array and
n.
So in this case n will be equal to six.
So that's why the vertices are from 0 to 5.
All right.
Now let's have our adjacency list over here.
All right.
So initially it's going to be an empty array an array with empty arrays.
Right.
So it's going to have six empty arrays.
So this is 01234 and five.
So which represents these five nodes.
So let's write the indices over here 0 to 5.
And then we are going to have our indegree array which is also going to have five elements.
And initially we are just going to fill zero for each index.
All right.
So we're just going to initialize it in this manner.
Now we will loop through our prerequisites array and we will fill our adjacency list.
So let's go ahead and do that.
All right, so how do we fill this?
We can see that there is a link from 0 to 5.
So that's why we have five over here.
And there is a link from 1 to 4 and two.
So we have four and two over here.
Now there is a there is no link going out from two.
So this is empty now from three we have two five and zero.
So 250 are there over here.
And then from four we have five.
So that's why we have five over here.
And then from five nothing goes out.
So this is how we build our adjacency list.
Now let's think about how to get the indegree factors for each of these nodes right.
Again we are just looping through the prerequisites array over here.
Now we can see that we have four comma one.
So this means that we have something coming in to four from one right.
So that means this link.
So before doing four we have to do one.
Or we can visualize it in this manner which is an edge which is coming into four.
So because we have four over here we are going to increment this by one.
So we get one over here.
Similarly over here we have two right.
So we are going to increment two by one.
And then over here again we have two.
So let's increment this again by one.
So we get two over here.
And we have five over here.
So we are going to increment the indegree factor of five by one.
And then we have five over here.
So let's again increment the indegree factor by one more.
So we have two over here.
Again we have five.
So we increment it once more.
We get three over here.
And then we have zero over here.
So we increment the indegree factor of this to one.
So now we have our indegree array and we have our adjacency list.
So this is going to be our first step.
All right.
Now we're just going to apply the topological sort algorithm which we discussed.
So first we take any vertex which has an indegree factor of zero.
So over here there are two vertices which have an indegree factor of zero.
So we can take any one of these right.
So let's take one for example.
Now when we take out one over here in the adjacency list we can see that its connections are to four
and two.
Right.
So for four and two we will reduce the indegree by one which are these two.
Right.
Because we are just removing this connection.
So we have to reduce the indegree factor for four and two by one.
So let's do that.
So four just has one and two just has two right.
So let's reduce one.
So over here this we have zero.
And over here we have two minus one which is equal to one.
All right.
Now we proceed.
So we have already taken out one.
Right now we take the next node which has an indegree factor of zero which is in this case we can take
3 or 4.
So let's just take four.
And we reduce the indegree factor of its connection.
So from four there is a connection of five.
So we can see that over here.
So we reduce this 3 to 2.
All right.
Now we again continue and take out the next node which has an indegree factor of zero.
All right.
So we have taken out one and four.
And three has an indegree factor of zero.
So let's take out three.
And the neighbors the edges from three are two five and zero.
So there is a connection going out from 3 to 2 five and zero.
So for two five and zero we will reduce the indegree factor by one right.
So we are doing that.
So for two we are getting one minus one which is zero.
For five we are getting two minus one which is one.
And for zero we are getting one minus one which is equal to zero.
All right.
So we have taken out three.
Now again let's continue and take out an element which has an indegree factor of zero which is among
zero and two.
We can take out any one.
So let's take out zero.
So if we take out zero we are going to decrement the indegree factor for five.
So this becomes also zero.
Now we have taken out zero and we are left with two and five.
And both of them have an indegree factor of zero.
So we can take out any one.
So we take out two and there is nothing to reduce.
You can see that again here.
It's empty so there is nothing to reduce.
And then we take the next one which is five.
And this is our topological sort.
Now once we apply the proper sort algorithm let's just count how many vertices we were able to visit.
You can see that 123456.
We were able to visit all the six vertices.
And n in this case also is equal to six right.
Which is 0 to 5.
So because the count is equal to n, we were able to visit all the vertices.
And that's why we can be sure that there is no cycle in the given graph.
If there was a cycle, then the count over here would have been less than six.
So this is how we are going to solve this question.
Now let's go ahead and write the remaining part of the pseudocode.
So the first step is we find the we create the adjacency list and the indegree factor array.
Now secondly we are going to take the vertices with indegree equal to zero.
And we will just push it to a stack.
All right.
Now we are going to have a while loop.
And this will loop as long as something is there in our stack.
Now once inside the while loop we will pop from the stack.
All right.
And then we will increment the count.
So whenever we pop from the stack we will increment the count.
So initially the count is going to be equal to zero.
And when we have one element inside it and we come inside for example, and then we pop at that time
count will be incremented to one.
And this goes on like that.
So we will trace this and take a look at it now.
After incrementing the count, what we will do is we will decrement the indegree factor for its neighbors
like we have seen over here, right?
For example, when we take out one, when we took out one, then we checked its neighbors, which is
four and two, and for four and two we decremented the indegree factor.
So the same thing is something that we are going to do over here.
So we will pop from the stack, we will increment the count and for its neighbors or for edges from
that node to the other nodes.
Right.
For those the edges coming into it, right for these neighbors.
So that's why for four and two, for example, over here we are going to decrement the indegree factor.
After decrementing the indegree factor.
We will check if the indegree factor for any of these nodes became zero, and if it became zero, we
will push it to our stack.
So this is going to be our pseudo code.
All right.
So if we have something we will push into the stack.
And then we will again check if there is something in our stack.
And then this goes on like that.
All right.
So this is how our code works.
Now if there is a cycle for example let's take an example.
Let's take a very simple example.
Let's say one and zero.
And then we have two.
And there is a clear cycle over here.
Now in this case n will be equal to three right n is equal to three.
So let's try to understand what would happen.
Let's again draw our adjacency list over here.
Now for zero there is only one edge going out of it.
So we would have two over here.
And then for one there is one going out which is to zero.
All right.
And then for two there is one edge going out from it to one.
So this is how our adjacency list would look like for this graph.
And then what would be the indegree factor.
Let's just write it over here.
For one the indegree factor is one for zero.
The indegree factor is one.
And then for two the Indegree factor is one.
All right.
Now if we go ahead and look at our code.
All right.
So just so that our code works, let's just uh okay, let's just continue and then we'll see why it
will stop immediately.
So at this point when we come to this step, we will see that there is nothing with indegree factor
zero.
Right.
So it will not even come inside and count is initialized to zero.
So when we come out, we will check whether count is equal to the number of vertices, which is three
and zero is not equal to three.
So we can be sure that there is a cycle.
And we know that we cannot complete the courses.
Now let's say n was equal to four.
All right.
So let's say n was equal to four.
And there is a vertex for over here which is not connected to anything.
So there is an indegree factor over here which is equal to zero.
All right.
So let's just have that also.
So at index four this is going to be index four.
There is nothing.
So again this part over here is going to be an empty array in our adjacency list.
Now what will happen is again we create our adjacency list and indegree factor array.
And then we will just push four to our stack.
We will come inside the while loop.
We will pop and count will change from 0 to 1.
And then we will decrement its neighbor.
So there is nothing to decrement.
And then we will check if there is something which can be pushed to the stack if its indegree is equal
to zero.
Right.
So we see nothing has an indegree factor of zero.
And then when we come over here we would we would not again go into the loop and we will come out right.
So again we can see count is equal to one.
And n in this case is equal to four.
So you can see we have seen a case where the count over here became equal to n right.
That was because all the vertices were visited.
And that happened because there is no cycle.
So this is how we are going to solve this question.
We will just implement the topple sort algorithm, and we will have a count to track how many vertices
where we were able to visit, or how many vertices by implementing the topple sort got an indegree factor
of zero at some point.
Now, if the count is equal to the number of vertices, then we can be sure there is no cycle.
And if the count is not equal to the number of vertices, then there is a cycle, and hence we cannot
complete all the questions.
And this is how we can solve this question.
Now let's take a quick look at the complexity analysis of this solution.
The time complexity of this solution is going to be of the order of p plus n plus e, where p is the
number of elements in the prerequisites array, and n is the number of vertices, and e is the number
of edges.
So let's try to understand why this is so.
And again you can notice this is much better than the previous time complexity which we got with the
brute force method.
Now let's try to understand this time complexity.
Now what are the things that take up time.
First of all we are going to form this adjacency list and indegree factor right.
So this will take some operations.
Now to form the adjacency list we will have to do p plus n operations right.
Because initially we will have to create an array with an empty arrays.
So that's why we have n operations over here.
Then we have to loop through the prerequisites array.
So that's why we have p operations over here.
And then fill the edges into the adjacency list.
So that's why to form the adjacency list we'll have to do p plus n operations.
And to get the indegree factor again right we have to go through the p uh prerequisites.
So we have to loop through them.
And again we have to initially form an array which is empty right.
Or and then we have.
To fill each of the places and places in that array with zero, and then we loop through the prerequisites
array and find the indegree factor for each vertex.
So over here also we are going to do p plus n operations.
So over here in step one we are going to do o of p plus an operations or a constant into p plus n operations.
All right.
Now what else takes up time.
So this part over here let's take a look at this part over here.
Also we are going to do a total of N plus E operations.
Why is that.
So this is the worst case that we're trying to think of.
Right.
So the worst case will happen if there is no cycle right.
So that means that every vertex at some point will come into the stack.
So we can say that this while loop over here is going to operate a total of n times, where n is the
number of vertices.
Now inside this we are going to decrement the neighbors by one right.
For each of these instances.
Now the neighbors will depend on the edges, right?
So when we come to zero, when we pop zero, we will only do one operation because we just have one.
When we pop one, we are going to do two operations.
When we pop three, we are going to do three operations.
When we pop four, we are going to do one operation, right.
So that's the total number of operations.
So let's just count it one, two, three, four, five, six and seven.
So this is seven operations.
And you can see that the number of edges over here is 7123456 and seven.
So over here we are going to do in total right.
The while loop is going to operate n times.
And when if you add the total operations of this part over across all these N operations of the while
loop, it's going to be equal to E.
That's why this part over here is going to have N plus E operations.
So that's why we will just add these two together.
And we get that the time complexity of this solution is of the order of p plus n plus e.
Again we have n and n.
So we can say two n but two is a constant.
So we just remove it and we get that.
The time complexity of this solution is of the order of p plus n plus e, p is the number of elements
in the prerequisite array, n is the number of vertices, and e is the number of edges.
Now what about the space complexity?
The space complexity of this solution is going to be of the order of n plus e, where n is the vertices
and e is the edges.
Right.
Because we are going to form this adjacency list.
Right.
So this adjacency list is going to have it is going to take space of the order of n plus E because it's
going to have n arrays right inside the array.
They are going to be n arrays.
And then the elements in those arrays will depend on the edges.
So that's what we are having over here.
Right.
So this is going to take space of the order of n plus e.
So that's why the space complexity of the solution is of the order of n plus e.
What are the other things that take up space.
So we can see that this indegree array is also taking up space which will be of the order of n that
is less than n plus e.
So we can neglect that we have this stack over here.
Now the stack will only contain elements which have an indegree factor of zero.
Now let's say the nodes were all disconnected so that every node has an indegree factor of zero.
In that case, the that would be the worst space complexity for the stack, and in the worst case,
the stack can take only O of n space complexity.
So that's why among all of these, this is the greatest space which is taken up.
And hence we can conclude that the space complexity of this solution is of the order of n plus e.
All right.
Now one last point to keep in mind is we have seen the time complexity is O of n plus p plus e.
The space complexity is O of n plus e.
Now, in the worst case E the number of edges can be of the order of n square.
All right.
So when will that happen?
Let's say our graph looks something like this.
Again it's a directed graph.
So from this node there is a connection to every other node.
And then from this node there is a connection to every other node except this node and so on and so
forth.
So we can say that there are n minus one connections over here, n minus two connections over here,
n minus three connections over here etc..
Right.
So in this case the total number of connections or edges would be n minus one plus n minus two, etc.
up to one which is equal to n minus one into n by two.
And this over here will have an n square term when we simplify it.
Therefore, this is going to be of the order of n square.
So we can see that the number of edges in the worst case possibility is going to be of the order of
n square.
So if we substitute that over here, we can see that the time complexity is going to be of the order
of p plus n square.
Right because we have an n, but among n and N square n square is going to be greater.
So we can neglect this.
And the space complexity is going to be of the order of just n square, because again we have n and
n square, and n square is going to be greater than n.
So we can say that in the worst case, the time complexity is going to be of the order of p plus n square,
and the space complexity is going to be of the order of n square.