Welcome back.
Now let's go ahead and think about the brute force method to solve this question.
We have already seen that if we can detect whether there is a cycle in the graph, then we can say that
we cannot complete all the courses.
So we are trying to think about how can we check if there is a cycle in the graph which is given to
us?
Now let's take an example.
Let's say n is equal to eight.
So the nodes are going to be from 0 to 7.
And let's say the graph looks like this.
All right so we can represent this.
The the prerequisite array which will be given to us would be looking like this.
Right.
So you can see there is a link.
Two comma one.
So this means that before doing two you have to do one.
So this is how we can visualize this.
And then we have three comma two which means before doing three you have to do two right.
Which is this link over here.
And before doing four you have to do three.
And before doing four you have to do two.
And before doing five you have to do zero.
And before doing six you have to do five, which is this link over here.
And then before doing zero you have to do six.
And then nothing is mentioned about seven, which means that it's just like this over here.
Not there's no edge with this from seven to any other node.
All right.
So this is how we have visualized the graph.
Now let's try to think about the brute force method of solving and checking whether there is a cycle
in this graph or not.
Now remember the graph can be unconnected.
All right.
So for example over here you can see this part over here.
Is not connected with these two other parts.
So the graph can be unconnected.
So this is something that you have to keep in mind when you come up with the brute force solution.
All right.
Now let's proceed.
Now we to start with we have the value of n.
And we have this array over here which is the prerequisites array.
Now using the prerequisites array and n let's form the adjacency list.
So this is going to be our first step.
We will form the adjacency list which is going to be an array of arrays.
So over here we will have the indices from 0 to 7.
Right.
So we have zero.
And we'll have an array over there.
And then we have one.
We have an array over there.
And this goes on till index seven.
So this is our adjacency list.
So we are going to form our adjacency list using n and this prerequisite array.
So for example at index zero there is a link to five.
So we will fill five over here.
And there is no other link.
Now at index one there is a link to two.
So we will fill two over here.
And at index seven there is no other link.
So this would be an empty array.
So this is our adjacency list.
So this would be the first thing that we will form.
Right.
And then because we we will need to know how to traverse the given graph.
Right.
So basically we will have to find a way to traverse the given graph.
And keeping in mind that the graph can be unconnected and check for cycles.
So this is what we are trying to do.
The first step is to form our adjacency list.
And then we will just take each vertex one by one.
And then we will do BFS or DFS.
That is we will traverse the graph from that particular vertex starting from that vertex.
And we can use breadth first search or depth first search.
It does not matter.
Right.
So we will do this.
And as we traverse the graph we will just check whether the vertex from which we started to traverse
the graph is appearing again in the traversal.
If it is appearing again, then we can be sure that we are seeing we have a cycle, and then if we have
a cycle, it just means that we cannot complete all the courses.
So this is the brute force method right?
So again why are we taking every vertex one by one?
It's because of the fact that the graph can be unconnected.
For example, if we start over here and if we do BFS or DFS, we will visit all these vertices and we
will see that there is no cycle.
Right?
There is no cycle at this point.
But then we cannot be sure that there is no cycle in all the graph, because you can see we have not
touched any of these vertices because this component and this component is unconnected.
Right.
So that's why we have to take each vertex one by one.
And then we have to traverse it.
So for example we will start over here.
We will traverse we'll see that there is no cycle.
But for example when we come over here and when we traverse, we will see that we will come to five
and then we'll come to six, and then we'll again come to one.
So we can see that the vertex from which we started is appearing again in the traversal, which means
that there is a cycle, and hence we cannot complete all the courses.
So this is how we are going to solve this question.
Now let's take a quick look at the space and time complexity of this solution.
Now let me just have a pointer mentioned over here.
The complexity analysis is going to be much easier to understand when we look at the code of this solution.
But let's try to discuss it over here.
First let's take a look at the time complexity.
So what are the things that take up time forming the adjacency list will take up time, right?
Because we first have to form an empty array of n elements.
So that's why we have n o of n over here.
And then we are going to iterate over the prerequisite array to form to fill the adjacency list, right.
To identify the edges and fill it into our adjacency list.
So that's why we are going to have O of n plus p operations to form the adjacency list, where n is
the number of vertices and p is the number of elements in our prerequisite array.
Again, why is that?
So over here we have n because initially we'll have to form an array of empty arrays.
And the elements is going to be n right.
They are going to be n empty arrays in the adjacency list array.
So that.
So to form that we will have to do n operations over here.
And then we will iterate through the prerequisite array and identify the edges and fill it to our adjacency
list.
So over here we are doing O of n plus p operations.
And then we are going to take each vertex one by one.
So there are n vertices.
So this is going to be an o of n operation.
And then we are going to check if the vertex is appearing in the traversal.
So basically we are going to take each vertex.
And then we are going to do BFS or DFS.
Now we know that the time complexity of BFS or DFS is O of n plus e, where n is the number of vertices.
Right?
Or we can say o of v plus e.
So we are going to do an O of v plus e operation in the worst case on each of these n vertices.
Why is that?
So the worst case is if all of the vertices are connected, right?
If all of them are connected, then for each of these vertices we will do o of n plus e number of operations.
So that's why taking this together right.
So for each of them we are doing N plus E operations.
So the total number of operations over here is going to be n into n plus e.
So let's add this and this together.
And we get that the time complexity is n plus p plus n into n plus e.
So this n over here is this n right.
So this is this n and n plus e is what we have over here which is what we have over here.
And again that's why we are multiplying them because for each of these we are doing n plus e operations
again.
So the time complexity is O of n plus p plus n into n plus e.
Now let's try to simplify this.
All right.
So let's try to simplify this.
We get n plus p plus.
N square plus NE.
Now n square is going to be greater than n.
So we can just avoid this.
And we can say that the time complexity is of the order of p plus n square plus n into e.
So this is the time complexity of this solution.
Now what about the space complexity of this solution.
Now what are the things that take up space that can scale?
When our input scales we are forming an adjacency list and then we are using a queue.
If we go ahead with the BFS solution.
Now in this part let's practice the breadth first search.
Right.
Because we have done questions for DFS previously.
So let's implement this with BFS.
So we can do it either BFS or DFS.
Now if you do it DFS then the stack would take up space if you do it iteratively.
And if you do DFS recursively, then the call stack will take up space.
So accordingly you have to consider the space complexity.
Now in this case we move ahead with BFS.
So the queue is going to take up space.
And then we have our visited object right.
So whenever we do BFS we will need a visited object so that we don't go ahead into an infinite loop.
So these are the things that take up space.
All right.
Now the adjacency list is going to be an array of arrays.
Right.
And the number of arrays inside the adjacency list will be equal to the number of vertices which is
equal to n.
And then inside this we are going to fill the edges right.
So that's why the space taken up by the adjacency list is going to be of the order of n plus e, where
n is the number of vertices and e is the number of edges.
So this is pretty straightforward.
And the queue is going to take up space of the order of n.
We know that for breadth first search, the queue.
In the worst case, possibility can take up space of the order of n, and the visited object is also
going to take up space of the order of N, because if even if we visit all the all the vertices right
in the same traversal.
So if all of them were connected and we visit all of them in one BFS traversal, then also the visited
object is going to take up O of n space.
So among all these three the greatest is n plus e.
So this is going to dominate right.
So the space complexity of this solution is going to be of the order of n plus e.
So we have seen that the time complexity is of the order of p plus n square plus n e.
And the space complexity is of the order of n plus E.
Right.
So we have seen this.
Now one more interesting thing to observe is that in the worst case in the graph, the number of edges
can be of the order of n square, where n is the number of vertices.
So let's try to understand this.
Let's say the graph looks something like this.
So this node is connected to every node.
Then this core this node over here is connected to every node except this one.
And this one is connected to every node except these two etc..
So it's going on like that.
So we can say that if there are n nodes then this node over here has n minus one connections and this
one has n minus two connections, this one has n minus three connections etc..
All right.
So again this is a directed graph.
So it goes in this way.
So these are the n minus one connections.
Then we have n minus two connections over here.
And then over here you can see we have n minus three connections.
And it goes on like that.
Now if we add this up n minus one plus n minus two etc. up to one right.
This is an arithmetic progression.
And we have seen that this is equal to n minus one into n minus one plus one, which is n divided by
two.
Right.
And this is um this on simplifying we have a term of n square.
Right.
Let's just simplify this.
We get n square minus n and we have by two by two.
So if we take the Big-O analysis or the asymptotic analysis of this, this is going to converge to O
of n square.
Right.
So that's why we can say that in the worst case the edges can be of the order of n square.
Now if we implement this over here, if we put this into our time and space complexity, we can write
n square over here.
And over here as well.
Right.
So in this case we can say that the time complexity is of the order of p plus n cubed.
Because we have n over here and n square.
So this becomes n cube.
So n cube is greater than n square.
So we can neglect this.
And we get p plus n cube over here.
And then the space complexity in this case becomes of the order of n square.
All right.
So you can explain both of these in the interview.
Again the if if the interviewer wants.
So again this is a good point to know.
So we have seen that the time complexity is of the order of p plus n square plus n e.
And if we take up the worst case possibility, we can say that that's of the order of p plus n cube.
And the space complexity is of the order of n plus e.
And if you take E as of to be of the order of n square, then we say that the space complexity is of
the order of n square.