Welcome back.
Let's now go ahead and write the brute force solution to check whether there is a cycle or whether we
can finish the courses.
So for this we will write a function and let's call it check if can finish.
All right.
So that's what we are checking.
And this function is going to take in n and it will take in the array which is the prerequisites.
So let's just call it prereqs.
All right.
Now inside this function first we will build the adjacency list.
So let's say const adjacency list is equal to and we will have a helper function to build the adjacency
list.
So let's say build adjacency list.
And over here we are going to pass n and the prereqs to it.
All right, now we have to write this function.
Let me just have a placeholder over here.
And then let's just finish this part.
So over here we have the function const and its build adjacency list.
And this function is going to take in n and the prereqs.
All right.
Now let's continue and finish this function over here.
And then we will come back and finish the helper function.
Now after we have built the adjacency list, we are going to loop through the vertices.
And for each vertex we are going to do a breadth first search and check if there is a uh there is a
cycle or not.
And again we can use breadth first search or depth first search.
Now over here we are just going to use BFS for practice.
We have already done a question with DFS before.
So let's continue.
Now over here I'm going to have a variable.
Let's say let has cycle.
And I'm going to return true for this.
If there is a cycle for that particular vertex when we're doing BFS.
So let's continue.
So we are going to loop through the vertices.
So let's say let vertex is equal to zero.
Vertex less than n.
Vertex plus plus.
So using this for loop we are going through the vertices.
All right.
Now we are going to say has cycle is equal.
To check let's have a helper function to check whether there is a cycle from that vertex including that
vertex.
And we are going to implement this with BFS.
So let's say check cycle BFS is the helper functions name.
And over here we are going to pass in the vertex.
And we will pass in the adjacency list which we have already built.
All right.
So this is going to return true if there is a cycle which includes that particular vertex.
So that vertex is the vertex where we are currently at in the for loop.
Now if has cycle is equal to true.
If half cycle is equal to true, then we can say that we cannot finish right, so we cannot finish the
courses.
So in that case we will just return false.
And if we are out of this for loop and we have not yet returned false, so as, as by that time, then
we can be sure that there is no cycle.
And at this point we will just return true, which indicates that yes, we can complete all the courses.
So this is how we will implement this.
And again we have to write this function also.
Right.
So let's just have a placeholder over here.
Const check cycle BFS.
So this is our function.
Now this function is going to take in the vertex and the graph.
So is equal to function.
And it's going to take in the vertex.
And the graph, which is the adjacency list.
All right.
Now let's go ahead and complete this solution for this.
We'll first write the build adjacency list function over here.
Let's complete this.
So inside this function we are going to have the adjacency list.
So const adjacency list is equal to.
So we are going to initialize this as an array.
So new array.
Of length n.
Where n is the number of vertices.
Right?
And then we are just going to fill zero at each position.
And then we are going to change each position to an empty array using the map operator.
All right.
So now we have created an empty adjacency list which is an array.
And each element in the array is an empty array.
So we have done this.
Now let's loop through the prerequisites.
So let's say for let prereq of prereqs.
So we are taking each value in the prereqs array which is given to us.
And each value is an array itself.
Right.
And it's, it's, it's of the form.
Let's say for example let's just have that.
Let me just make an example over here.
Let's say an element is one comma two in prereqs.
So this means that to do one first we have to do two.
Or it means that we can do one only after doing two.
So that's what this means.
Right now we are going to take each prereqs or each element in the prereqs array, which is going to
be of this form.
Right.
And you can see that this is of the form to take and first take.
So we have to first take two to take two to take one.
Right.
So let's just write this as const.
And I'm just naming the variables to take.
And first take.
Right.
So this is of this form, right.
Because you can see you have to first take two to be able to take one.
So that is visible because we have visualized this over here.
So this is going to be equal to prereqs Prereq.
Right.
That particular Prereq.
Now again you could just do prereq at zero and prereq at one.
And then you can you can say two take is equal to prereq at zero.
And first take is equal to prereq at one.
So this is the same thing that we're doing over here.
All right.
Now after we have done this we are just going to push the respective edge the connection to our adjacency
list.
So adjacency list at first take right at first take.
Is going.
And then over here we are going to push dot push to take.
All right, so what did we just now do?
So you over here, let's just take this example over here.
Now this can be visualized like this.
Right.
Two.
Then you have an arrow two one.
So at two right which is equal to first take we are going to add one which is two take to that particular
part in the adjacency list.
So let's just have an example.
Let's just take a look at this itself.
All right.
So first take in this case is equal to two.
Right.
So this is zero.
This is one this is two.
All right.
And then it goes on like this.
So this is just our adjacency list which is an array of arrays.
And I'm just visualizing it over here.
Now in this example where we have one comma two, we have seen that we have to first take two to be
able to take one.
So it can be visualized like this.
So at index two which is this one over here we are going to insert two take which is one.
So this is what we are doing over here Adjacencylist at first take dot push to take right.
So in this way we are going to build our adjacency list.
Now once we are out of this we're just going to return the adjacency list.
Now again, we're we're not inserting in previous examples we have seen that we are doing it both ways.
Right.
But over here we are dealing with a directed graph.
So that's why only in the case for example two is pointing to one.
So at two we will insert one.
So that is what we are doing over here.
Now we have built our adjacency list and it's going to get returned.
So this part over here is done right.
So now we are just have to write our BFS function to traverse and check whether there is a cycle involved
with that particular vertex.
So let's go ahead and complete this part.
Now once we are inside this function we will need a queue because we are doing BFS right.
And we always use a queue for breadth first search.
Now again mentioned to the interviewer that we are implementing the queue as an array just to save time.
Ideally, to get the optimum time complexity, we have to implement the queue as a linked list in JavaScript
because there is no inbuilt queue data structure in JavaScript.
So again, remember you have to mention this to your interviewer.
But because again, this is not the central thing that is being tested in this question.
So to save time we're just implementing the queue as an array over here.
And then we will need our visited object to keep track whether a particular vertex is visited or not,
so that we don't get caught in a cycle.
All right.
And then we are just going to loop through the what the, the neighbors of that particular vertex.
And we will add it to our queue.
So for let I is equal to zero.
I less than graph.
At that particular vertex.
So this will give us all the connections, right?
For example, if we were at I is equal to two then we will get one over here.
Right.
Because two is having a link to one.
So I less than graph at vertex dot length.
So that that will give us the number of connections which are outgoing from vertex I right.
And then I plus plus.
All right.
So now for each of these, these edges, we are just going to push that particular vertex to our q.
So q dot push graph.
At vertex at.
I write because we just want one at a time.
So we are going to push the respective vertices to our queue.
And then once we are out of this, we are going to have a while loop.
So while something is there in the queue.
First, we will shift or take out from the beginning of the queue or we are d queuing.
So we say const car, let's just call it car is equal to q dot shift.
So this is what we always do with BFS right?
We are implementing breadth first search over here.
And then we will just mark car as true visited at car is equal to true.
So we have visited this.
Now what we will do is we actually have implemented this BFS to see whether there is a cycle involving
this particular vertex.
Right.
So if car is equal to this vertex then we have met a cycle.
Right.
So we are we have encountered a cycle.
And in that case we can return true which indicates that yes there is a cycle with this vertex.
So in the part of the graph along with this vertex.
So that is what we identified if car is equal to vertex.
So let's just check that.
So if car.
Is equal to vertex.
In that case, we have identified a cycle and we can just return true.
Now, if this is not the case, then we proceed.
So we identify the neighbors.
Of this particular vertex curve.
So neighbors is equal to graph.
At Coeur.
So this will give us an array.
Right.
And then we're just going to loop through the elements in this array.
So let's say for let j is equal to zero j less than.
Neighbors dot length.
J plus plus.
And then we will just check whether the particular neighbor has been visited.
So let's just say const neighbor.
Is equal to neighbors at J.
So we are taking that particular neighbor, and now we are going to check if it's there in our visited
object.
So if not visited at neighbor.
So if it's not visited then we will push it to our queue.
So we'll say queue dot push.
Neighbor.
All right.
So this is our BFS.
Now if we come out of this while loop and we have not yet identified a cycle.
So that means that there is no cycle and we can just return false.
All right.
So that brings us to the end of this function.
So we are done with our solution.
So we have right we have written our check if can finish function.
And this function calls the build adjacency list helper function to get our adjacency list.
Now we are just looping through every vertex, and for each vertex we call the check cycle BFS function.
And we are checking whether there is a cycle along with that vertex.
Now we are doing this because the uh the vertices there can be unconnected components also.
Right.
So that's why we are looping through all the vertices and calling the check cycle BFS.
Because this again is our brute force solution.
Now if there is a cycle this would return true.
So if it is returning true then we can return false from this function because it means that we cannot
finish all the courses.
Now let's go ahead and test our function and let's see whether it's working.
Now for this we will call this function check if can finish.
And we have to pass in N and we have to pass in an array of prerequisites.
Right.
So let's just call it prerequisites over here as well.
So now let's define n.
Let's say n is equal to two.
Let's have a very simple example to begin with and let's say prereqs.
So over here I'm saying let n is equal to two.
And let's say prereqs is equal to.
An array of arrays.
So initially I have zero comma one.
This means that I have to first take one to do zero right.
So let's just visualize this as well.
So I'm going to write it over here.
So this means I have to first take one to be able to do zero.
Now let's say there is one more element over here which is one comma zero.
So this means I have to.
First do zero to be able to take one.
So there is a cycle right.
So this is a very simple example where there is a clear cycle.
Now when we call this function we our expectation is that we should get false.
So let's go ahead and call our function.
And let's take a look at our output.
And we are getting false.
So this this is correct.
So we cannot finish it.
Now let's have a few more examples and take a look at our code.
Now I'm going to have a bigger example.
So first before we give the input let's just draw it out so that we can visualize this.
So let's go ahead and draw it.
All right.
So let me just grab a pen.
Now let's say n is equal to five.
Let's say n is equal to five.
And let's say we have the nodes zero which is connected to one which is connected to two.
And let's say two is connected to three.
And let's say three is connected to one.
All right.
Now still we don't have any cycle.
Right.
And then let's say we just have four also.
So let's say two is connected to four.
Now if this is the graph which is given to us it should return true true right.
Because there is no cycle.
Again this is not a cycle.
This is not a cycle because this is the direction from 0 to 1.
And then we have this way.
All right.
So this should be possible.
So let's go ahead and give this input and check whether our code is working.
So in this case n is equal to five.
And let's give let's create the prereq array.
So prereqs array.
So we have a link from 0 to 1.
So let's write that.
So we have one comma zero.
Which means to do one, we have to do zero.
Let's continue.
Now we have this over here from 0 to 2.
Right.
So this means we have two comma zero.
And.
Then we have this link over here from 2 to 3.
So this means three comma two.
Then we have this link over here from 3 to 1.
Right.
So we have one comma three.
And then we have this link over here from 2 to 4.
So that means that's four comma two right.
So that's four comma two.
So 12345.
And we have five elements over here.
All right.
Now let's go ahead and run our code and see what's the output that we are getting.
Now.
We are getting true which is correct.
Right.
So this is possible.
So this is correct.
Now let's just change the direction of this from 0 to 1.
So let me just change this.
So I'm taking a pen.
Let's change this in this way.
So from one 1 to 0.
So over here if we have this in this direction there is a clear cycle.
And this should return false.
So let's go ahead and try this.
So this one over here I'm just changing it to zero comma one.
And let's run our code and we get false.
So this is a cycle.
So we have identified this and it's not possible.
So yes our code is working.
Now let's also take an example where we have an unconnected component.
So I'm changing this back.
All right.
So I'm changing this back.
So let's have.
This in this direction itself.
And over here, let's just have, um.
Five.
And six.
So 6 to 5.
And let's say we have seven also over here.
So let's add this part also to our input and see whether it's working.
So I'm changing this back to one comma zero.
All right.
Now over here n is equal to eight.
And let's add these connections.
So there is a connection from 6 to 5 right.
So that's five comma six.
And there is a connection from 5 to 7.
So that is seven comma five.
And there is a connection from 7 to 6.
Right.
So that's six comma seven.
So this should give us the output as false.
So let's try it.
Yes that's false.
It's identifying that there is a cycle over here.
So yes our code is working.