1
00:00:00,580 --> 00:00:01,600
Welcome back.

2
00:00:01,600 --> 00:00:07,930
Let's now go ahead and write the brute force solution to check whether there is a cycle or whether we

3
00:00:07,930 --> 00:00:09,430
can finish the courses.

4
00:00:09,430 --> 00:00:15,100
So for this we will write a function and let's call it check if can finish.

5
00:00:15,100 --> 00:00:15,370
All right.

6
00:00:15,370 --> 00:00:16,840
So that's what we are checking.

7
00:00:16,840 --> 00:00:23,470
And this function is going to take in n and it will take in the array which is the prerequisites.

8
00:00:23,470 --> 00:00:25,300
So let's just call it prereqs.

9
00:00:25,870 --> 00:00:26,290
All right.

10
00:00:26,320 --> 00:00:30,580
Now inside this function first we will build the adjacency list.

11
00:00:30,580 --> 00:00:37,120
So let's say const adjacency list is equal to and we will have a helper function to build the adjacency

12
00:00:37,120 --> 00:00:37,330
list.

13
00:00:37,330 --> 00:00:39,730
So let's say build adjacency list.

14
00:00:39,940 --> 00:00:43,840
And over here we are going to pass n and the prereqs to it.

15
00:00:44,750 --> 00:00:47,060
All right, now we have to write this function.

16
00:00:47,060 --> 00:00:48,860
Let me just have a placeholder over here.

17
00:00:48,860 --> 00:00:50,390
And then let's just finish this part.

18
00:00:50,390 --> 00:00:55,190
So over here we have the function const and its build adjacency list.

19
00:00:55,190 --> 00:00:59,240
And this function is going to take in n and the prereqs.

20
00:01:01,620 --> 00:01:02,070
All right.

21
00:01:02,070 --> 00:01:04,380
Now let's continue and finish this function over here.

22
00:01:04,380 --> 00:01:07,350
And then we will come back and finish the helper function.

23
00:01:07,350 --> 00:01:12,420
Now after we have built the adjacency list, we are going to loop through the vertices.

24
00:01:12,420 --> 00:01:18,540
And for each vertex we are going to do a breadth first search and check if there is a uh there is a

25
00:01:18,540 --> 00:01:19,320
cycle or not.

26
00:01:19,320 --> 00:01:22,590
And again we can use breadth first search or depth first search.

27
00:01:22,590 --> 00:01:25,590
Now over here we are just going to use BFS for practice.

28
00:01:25,590 --> 00:01:28,200
We have already done a question with DFS before.

29
00:01:28,200 --> 00:01:29,490
So let's continue.

30
00:01:29,970 --> 00:01:32,040
Now over here I'm going to have a variable.

31
00:01:32,040 --> 00:01:34,560
Let's say let has cycle.

32
00:01:35,910 --> 00:01:39,240
And I'm going to return true for this.

33
00:01:39,270 --> 00:01:43,140
If there is a cycle for that particular vertex when we're doing BFS.

34
00:01:43,140 --> 00:01:44,190
So let's continue.

35
00:01:44,190 --> 00:01:46,080
So we are going to loop through the vertices.

36
00:01:46,080 --> 00:01:49,740
So let's say let vertex is equal to zero.

37
00:01:50,920 --> 00:01:52,990
Vertex less than n.

38
00:01:53,910 --> 00:01:55,410
Vertex plus plus.

39
00:01:55,800 --> 00:01:59,430
So using this for loop we are going through the vertices.

40
00:01:59,430 --> 00:01:59,850
All right.

41
00:01:59,880 --> 00:02:02,550
Now we are going to say has cycle is equal.

42
00:02:02,550 --> 00:02:08,820
To check let's have a helper function to check whether there is a cycle from that vertex including that

43
00:02:08,820 --> 00:02:09,330
vertex.

44
00:02:09,330 --> 00:02:11,670
And we are going to implement this with BFS.

45
00:02:11,670 --> 00:02:15,810
So let's say check cycle BFS is the helper functions name.

46
00:02:15,810 --> 00:02:18,000
And over here we are going to pass in the vertex.

47
00:02:18,000 --> 00:02:21,270
And we will pass in the adjacency list which we have already built.

48
00:02:21,270 --> 00:02:21,660
All right.

49
00:02:21,660 --> 00:02:27,030
So this is going to return true if there is a cycle which includes that particular vertex.

50
00:02:27,030 --> 00:02:31,320
So that vertex is the vertex where we are currently at in the for loop.

51
00:02:31,320 --> 00:02:34,590
Now if has cycle is equal to true.

52
00:02:35,420 --> 00:02:40,970
If half cycle is equal to true, then we can say that we cannot finish right, so we cannot finish the

53
00:02:40,970 --> 00:02:41,510
courses.

54
00:02:41,510 --> 00:02:44,330
So in that case we will just return false.

55
00:02:44,420 --> 00:02:51,020
And if we are out of this for loop and we have not yet returned false, so as, as by that time, then

56
00:02:51,020 --> 00:02:52,970
we can be sure that there is no cycle.

57
00:02:52,970 --> 00:02:58,370
And at this point we will just return true, which indicates that yes, we can complete all the courses.

58
00:02:58,370 --> 00:03:00,140
So this is how we will implement this.

59
00:03:00,140 --> 00:03:02,030
And again we have to write this function also.

60
00:03:02,030 --> 00:03:02,180
Right.

61
00:03:02,180 --> 00:03:04,100
So let's just have a placeholder over here.

62
00:03:05,170 --> 00:03:07,510
Const check cycle BFS.

63
00:03:07,510 --> 00:03:09,040
So this is our function.

64
00:03:09,040 --> 00:03:12,370
Now this function is going to take in the vertex and the graph.

65
00:03:12,370 --> 00:03:14,140
So is equal to function.

66
00:03:14,140 --> 00:03:16,360
And it's going to take in the vertex.

67
00:03:17,120 --> 00:03:19,670
And the graph, which is the adjacency list.

68
00:03:21,500 --> 00:03:21,950
All right.

69
00:03:21,980 --> 00:03:24,800
Now let's go ahead and complete this solution for this.

70
00:03:24,830 --> 00:03:28,160
We'll first write the build adjacency list function over here.

71
00:03:28,160 --> 00:03:29,330
Let's complete this.

72
00:03:29,330 --> 00:03:33,590
So inside this function we are going to have the adjacency list.

73
00:03:33,590 --> 00:03:35,930
So const adjacency list is equal to.

74
00:03:35,930 --> 00:03:38,000
So we are going to initialize this as an array.

75
00:03:38,000 --> 00:03:38,930
So new array.

76
00:03:39,880 --> 00:03:41,050
Of length n.

77
00:03:42,460 --> 00:03:44,020
Where n is the number of vertices.

78
00:03:44,020 --> 00:03:44,470
Right?

79
00:03:44,470 --> 00:03:48,460
And then we are just going to fill zero at each position.

80
00:03:48,460 --> 00:03:54,010
And then we are going to change each position to an empty array using the map operator.

81
00:03:58,810 --> 00:03:59,230
All right.

82
00:03:59,230 --> 00:04:03,700
So now we have created an empty adjacency list which is an array.

83
00:04:03,700 --> 00:04:06,880
And each element in the array is an empty array.

84
00:04:06,880 --> 00:04:07,840
So we have done this.

85
00:04:07,840 --> 00:04:10,180
Now let's loop through the prerequisites.

86
00:04:10,180 --> 00:04:14,980
So let's say for let prereq of prereqs.

87
00:04:14,980 --> 00:04:19,150
So we are taking each value in the prereqs array which is given to us.

88
00:04:19,150 --> 00:04:22,210
And each value is an array itself.

89
00:04:22,210 --> 00:04:22,600
Right.

90
00:04:22,600 --> 00:04:24,640
And it's, it's, it's of the form.

91
00:04:24,640 --> 00:04:26,500
Let's say for example let's just have that.

92
00:04:26,500 --> 00:04:28,720
Let me just make an example over here.

93
00:04:28,720 --> 00:04:32,560
Let's say an element is one comma two in prereqs.

94
00:04:32,560 --> 00:04:36,340
So this means that to do one first we have to do two.

95
00:04:36,340 --> 00:04:40,000
Or it means that we can do one only after doing two.

96
00:04:40,030 --> 00:04:41,830
So that's what this means.

97
00:04:41,830 --> 00:04:47,980
Right now we are going to take each prereqs or each element in the prereqs array, which is going to

98
00:04:47,980 --> 00:04:48,910
be of this form.

99
00:04:48,910 --> 00:04:49,330
Right.

100
00:04:49,330 --> 00:04:53,020
And you can see that this is of the form to take and first take.

101
00:04:53,020 --> 00:04:55,840
So we have to first take two to take two to take one.

102
00:04:55,840 --> 00:04:56,140
Right.

103
00:04:56,140 --> 00:04:58,390
So let's just write this as const.

104
00:04:59,480 --> 00:05:02,360
And I'm just naming the variables to take.

105
00:05:04,280 --> 00:05:05,750
And first take.

106
00:05:08,550 --> 00:05:08,910
Right.

107
00:05:08,910 --> 00:05:10,290
So this is of this form, right.

108
00:05:10,290 --> 00:05:15,000
Because you can see you have to first take two to be able to take one.

109
00:05:15,000 --> 00:05:17,640
So that is visible because we have visualized this over here.

110
00:05:17,640 --> 00:05:21,750
So this is going to be equal to prereqs Prereq.

111
00:05:21,750 --> 00:05:21,960
Right.

112
00:05:21,960 --> 00:05:23,250
That particular Prereq.

113
00:05:23,250 --> 00:05:27,600
Now again you could just do prereq at zero and prereq at one.

114
00:05:27,600 --> 00:05:31,830
And then you can you can say two take is equal to prereq at zero.

115
00:05:31,830 --> 00:05:34,440
And first take is equal to prereq at one.

116
00:05:34,440 --> 00:05:36,180
So this is the same thing that we're doing over here.

117
00:05:36,180 --> 00:05:36,720
All right.

118
00:05:36,720 --> 00:05:43,140
Now after we have done this we are just going to push the respective edge the connection to our adjacency

119
00:05:43,140 --> 00:05:43,380
list.

120
00:05:43,380 --> 00:05:46,800
So adjacency list at first take right at first take.

121
00:05:48,370 --> 00:05:49,030
Is going.

122
00:05:49,030 --> 00:05:52,870
And then over here we are going to push dot push to take.

123
00:05:55,140 --> 00:05:56,790
All right, so what did we just now do?

124
00:05:56,790 --> 00:06:00,060
So you over here, let's just take this example over here.

125
00:06:00,060 --> 00:06:02,190
Now this can be visualized like this.

126
00:06:02,190 --> 00:06:02,460
Right.

127
00:06:02,460 --> 00:06:02,790
Two.

128
00:06:02,820 --> 00:06:04,110
Then you have an arrow two one.

129
00:06:04,110 --> 00:06:11,970
So at two right which is equal to first take we are going to add one which is two take to that particular

130
00:06:11,970 --> 00:06:13,440
part in the adjacency list.

131
00:06:13,440 --> 00:06:14,970
So let's just have an example.

132
00:06:14,970 --> 00:06:17,310
Let's just take a look at this itself.

133
00:06:17,310 --> 00:06:17,760
All right.

134
00:06:17,760 --> 00:06:22,350
So first take in this case is equal to two.

135
00:06:22,350 --> 00:06:22,560
Right.

136
00:06:22,560 --> 00:06:24,240
So this is zero.

137
00:06:24,750 --> 00:06:27,450
This is one this is two.

138
00:06:28,110 --> 00:06:28,380
All right.

139
00:06:28,380 --> 00:06:29,760
And then it goes on like this.

140
00:06:29,760 --> 00:06:33,540
So this is just our adjacency list which is an array of arrays.

141
00:06:34,260 --> 00:06:35,880
And I'm just visualizing it over here.

142
00:06:35,880 --> 00:06:41,640
Now in this example where we have one comma two, we have seen that we have to first take two to be

143
00:06:41,640 --> 00:06:42,540
able to take one.

144
00:06:42,540 --> 00:06:44,640
So it can be visualized like this.

145
00:06:44,640 --> 00:06:49,710
So at index two which is this one over here we are going to insert two take which is one.

146
00:06:49,710 --> 00:06:55,140
So this is what we are doing over here Adjacencylist at first take dot push to take right.

147
00:06:55,140 --> 00:06:57,720
So in this way we are going to build our adjacency list.

148
00:06:57,750 --> 00:07:02,100
Now once we are out of this we're just going to return the adjacency list.

149
00:07:03,150 --> 00:07:08,130
Now again, we're we're not inserting in previous examples we have seen that we are doing it both ways.

150
00:07:08,130 --> 00:07:08,460
Right.

151
00:07:08,460 --> 00:07:10,800
But over here we are dealing with a directed graph.

152
00:07:10,800 --> 00:07:14,700
So that's why only in the case for example two is pointing to one.

153
00:07:14,700 --> 00:07:16,560
So at two we will insert one.

154
00:07:16,560 --> 00:07:17,940
So that is what we are doing over here.

155
00:07:17,940 --> 00:07:21,900
Now we have built our adjacency list and it's going to get returned.

156
00:07:21,900 --> 00:07:23,880
So this part over here is done right.

157
00:07:23,880 --> 00:07:30,330
So now we are just have to write our BFS function to traverse and check whether there is a cycle involved

158
00:07:30,330 --> 00:07:31,710
with that particular vertex.

159
00:07:31,710 --> 00:07:33,660
So let's go ahead and complete this part.

160
00:07:34,140 --> 00:07:38,820
Now once we are inside this function we will need a queue because we are doing BFS right.

161
00:07:38,820 --> 00:07:41,430
And we always use a queue for breadth first search.

162
00:07:41,430 --> 00:07:47,070
Now again mentioned to the interviewer that we are implementing the queue as an array just to save time.

163
00:07:48,030 --> 00:07:54,900
Ideally, to get the optimum time complexity, we have to implement the queue as a linked list in JavaScript

164
00:07:54,900 --> 00:07:59,070
because there is no inbuilt queue data structure in JavaScript.

165
00:07:59,070 --> 00:08:01,740
So again, remember you have to mention this to your interviewer.

166
00:08:01,740 --> 00:08:05,730
But because again, this is not the central thing that is being tested in this question.

167
00:08:05,730 --> 00:08:09,930
So to save time we're just implementing the queue as an array over here.

168
00:08:09,930 --> 00:08:16,530
And then we will need our visited object to keep track whether a particular vertex is visited or not,

169
00:08:16,530 --> 00:08:19,170
so that we don't get caught in a cycle.

170
00:08:19,170 --> 00:08:19,590
All right.

171
00:08:19,590 --> 00:08:24,840
And then we are just going to loop through the what the, the neighbors of that particular vertex.

172
00:08:24,840 --> 00:08:26,670
And we will add it to our queue.

173
00:08:26,670 --> 00:08:29,460
So for let I is equal to zero.

174
00:08:30,310 --> 00:08:32,380
I less than graph.

175
00:08:33,690 --> 00:08:35,310
At that particular vertex.

176
00:08:35,310 --> 00:08:38,190
So this will give us all the connections, right?

177
00:08:38,220 --> 00:08:43,380
For example, if we were at I is equal to two then we will get one over here.

178
00:08:43,380 --> 00:08:43,650
Right.

179
00:08:43,650 --> 00:08:45,630
Because two is having a link to one.

180
00:08:45,630 --> 00:08:49,440
So I less than graph at vertex dot length.

181
00:08:51,040 --> 00:08:56,770
So that that will give us the number of connections which are outgoing from vertex I right.

182
00:08:56,770 --> 00:08:58,210
And then I plus plus.

183
00:09:00,010 --> 00:09:00,280
All right.

184
00:09:00,280 --> 00:09:06,310
So now for each of these, these edges, we are just going to push that particular vertex to our q.

185
00:09:06,310 --> 00:09:09,070
So q dot push graph.

186
00:09:11,270 --> 00:09:13,460
At vertex at.

187
00:09:13,460 --> 00:09:17,870
I write because we just want one at a time.

188
00:09:17,870 --> 00:09:21,800
So we are going to push the respective vertices to our queue.

189
00:09:21,800 --> 00:09:25,880
And then once we are out of this, we are going to have a while loop.

190
00:09:25,970 --> 00:09:28,220
So while something is there in the queue.

191
00:09:30,250 --> 00:09:34,750
First, we will shift or take out from the beginning of the queue or we are d queuing.

192
00:09:34,750 --> 00:09:41,170
So we say const car, let's just call it car is equal to q dot shift.

193
00:09:41,170 --> 00:09:43,630
So this is what we always do with BFS right?

194
00:09:43,630 --> 00:09:45,910
We are implementing breadth first search over here.

195
00:09:45,910 --> 00:09:51,190
And then we will just mark car as true visited at car is equal to true.

196
00:09:51,190 --> 00:09:52,480
So we have visited this.

197
00:09:52,900 --> 00:10:01,090
Now what we will do is we actually have implemented this BFS to see whether there is a cycle involving

198
00:10:01,090 --> 00:10:02,290
this particular vertex.

199
00:10:02,290 --> 00:10:02,590
Right.

200
00:10:02,590 --> 00:10:06,250
So if car is equal to this vertex then we have met a cycle.

201
00:10:06,250 --> 00:10:06,430
Right.

202
00:10:06,430 --> 00:10:08,380
So we are we have encountered a cycle.

203
00:10:08,380 --> 00:10:14,530
And in that case we can return true which indicates that yes there is a cycle with this vertex.

204
00:10:14,530 --> 00:10:17,110
So in the part of the graph along with this vertex.

205
00:10:17,110 --> 00:10:19,990
So that is what we identified if car is equal to vertex.

206
00:10:19,990 --> 00:10:21,400
So let's just check that.

207
00:10:21,400 --> 00:10:22,420
So if car.

208
00:10:23,700 --> 00:10:25,200
Is equal to vertex.

209
00:10:26,060 --> 00:10:30,320
In that case, we have identified a cycle and we can just return true.

210
00:10:30,980 --> 00:10:33,560
Now, if this is not the case, then we proceed.

211
00:10:33,560 --> 00:10:35,780
So we identify the neighbors.

212
00:10:37,270 --> 00:10:39,460
Of this particular vertex curve.

213
00:10:39,460 --> 00:10:41,920
So neighbors is equal to graph.

214
00:10:42,560 --> 00:10:43,310
At Coeur.

215
00:10:45,020 --> 00:10:46,550
So this will give us an array.

216
00:10:46,550 --> 00:10:46,970
Right.

217
00:10:46,970 --> 00:10:49,940
And then we're just going to loop through the elements in this array.

218
00:10:49,940 --> 00:10:54,650
So let's say for let j is equal to zero j less than.

219
00:10:55,370 --> 00:10:57,200
Neighbors dot length.

220
00:10:58,260 --> 00:10:59,610
J plus plus.

221
00:11:00,760 --> 00:11:05,260
And then we will just check whether the particular neighbor has been visited.

222
00:11:05,260 --> 00:11:07,480
So let's just say const neighbor.

223
00:11:09,090 --> 00:11:12,570
Is equal to neighbors at J.

224
00:11:14,590 --> 00:11:19,840
So we are taking that particular neighbor, and now we are going to check if it's there in our visited

225
00:11:19,840 --> 00:11:20,200
object.

226
00:11:20,200 --> 00:11:22,960
So if not visited at neighbor.

227
00:11:23,860 --> 00:11:27,130
So if it's not visited then we will push it to our queue.

228
00:11:27,130 --> 00:11:28,690
So we'll say queue dot push.

229
00:11:30,440 --> 00:11:31,220
Neighbor.

230
00:11:33,120 --> 00:11:33,390
All right.

231
00:11:33,390 --> 00:11:34,860
So this is our BFS.

232
00:11:34,890 --> 00:11:40,500
Now if we come out of this while loop and we have not yet identified a cycle.

233
00:11:40,500 --> 00:11:44,760
So that means that there is no cycle and we can just return false.

234
00:11:45,710 --> 00:11:45,980
All right.

235
00:11:45,980 --> 00:11:48,140
So that brings us to the end of this function.

236
00:11:48,140 --> 00:11:49,910
So we are done with our solution.

237
00:11:49,910 --> 00:11:53,930
So we have right we have written our check if can finish function.

238
00:11:53,930 --> 00:11:59,660
And this function calls the build adjacency list helper function to get our adjacency list.

239
00:11:59,660 --> 00:12:06,170
Now we are just looping through every vertex, and for each vertex we call the check cycle BFS function.

240
00:12:06,170 --> 00:12:09,590
And we are checking whether there is a cycle along with that vertex.

241
00:12:09,590 --> 00:12:14,630
Now we are doing this because the uh the vertices there can be unconnected components also.

242
00:12:14,630 --> 00:12:14,900
Right.

243
00:12:14,900 --> 00:12:18,800
So that's why we are looping through all the vertices and calling the check cycle BFS.

244
00:12:18,800 --> 00:12:21,260
Because this again is our brute force solution.

245
00:12:21,260 --> 00:12:24,710
Now if there is a cycle this would return true.

246
00:12:24,710 --> 00:12:30,740
So if it is returning true then we can return false from this function because it means that we cannot

247
00:12:30,740 --> 00:12:32,000
finish all the courses.

248
00:12:32,000 --> 00:12:35,390
Now let's go ahead and test our function and let's see whether it's working.

249
00:12:35,390 --> 00:12:39,050
Now for this we will call this function check if can finish.

250
00:12:39,760 --> 00:12:44,920
And we have to pass in N and we have to pass in an array of prerequisites.

251
00:12:44,920 --> 00:12:45,370
Right.

252
00:12:45,370 --> 00:12:48,280
So let's just call it prerequisites over here as well.

253
00:12:48,280 --> 00:12:49,930
So now let's define n.

254
00:12:49,930 --> 00:12:51,850
Let's say n is equal to two.

255
00:12:51,850 --> 00:12:55,690
Let's have a very simple example to begin with and let's say prereqs.

256
00:12:55,690 --> 00:12:58,360
So over here I'm saying let n is equal to two.

257
00:12:58,360 --> 00:13:01,660
And let's say prereqs is equal to.

258
00:13:03,110 --> 00:13:04,130
An array of arrays.

259
00:13:04,130 --> 00:13:06,020
So initially I have zero comma one.

260
00:13:06,020 --> 00:13:09,680
This means that I have to first take one to do zero right.

261
00:13:09,680 --> 00:13:11,810
So let's just visualize this as well.

262
00:13:11,810 --> 00:13:12,980
So I'm going to write it over here.

263
00:13:12,980 --> 00:13:16,610
So this means I have to first take one to be able to do zero.

264
00:13:16,760 --> 00:13:21,200
Now let's say there is one more element over here which is one comma zero.

265
00:13:21,650 --> 00:13:23,900
So this means I have to.

266
00:13:24,520 --> 00:13:27,580
First do zero to be able to take one.

267
00:13:27,970 --> 00:13:29,110
So there is a cycle right.

268
00:13:29,110 --> 00:13:32,740
So this is a very simple example where there is a clear cycle.

269
00:13:32,740 --> 00:13:36,850
Now when we call this function we our expectation is that we should get false.

270
00:13:36,850 --> 00:13:38,710
So let's go ahead and call our function.

271
00:13:38,710 --> 00:13:40,450
And let's take a look at our output.

272
00:13:40,450 --> 00:13:41,380
And we are getting false.

273
00:13:41,380 --> 00:13:42,850
So this this is correct.

274
00:13:42,850 --> 00:13:44,020
So we cannot finish it.

275
00:13:44,020 --> 00:13:48,190
Now let's have a few more examples and take a look at our code.

276
00:13:48,610 --> 00:13:50,830
Now I'm going to have a bigger example.

277
00:13:50,830 --> 00:13:55,990
So first before we give the input let's just draw it out so that we can visualize this.

278
00:13:55,990 --> 00:13:57,880
So let's go ahead and draw it.

279
00:13:58,360 --> 00:13:58,720
All right.

280
00:13:58,720 --> 00:14:00,550
So let me just grab a pen.

281
00:14:00,550 --> 00:14:03,250
Now let's say n is equal to five.

282
00:14:03,250 --> 00:14:04,960
Let's say n is equal to five.

283
00:14:04,960 --> 00:14:10,390
And let's say we have the nodes zero which is connected to one which is connected to two.

284
00:14:10,390 --> 00:14:12,490
And let's say two is connected to three.

285
00:14:12,490 --> 00:14:17,170
And let's say three is connected to one.

286
00:14:17,170 --> 00:14:17,590
All right.

287
00:14:17,620 --> 00:14:19,930
Now still we don't have any cycle.

288
00:14:19,930 --> 00:14:20,260
Right.

289
00:14:20,260 --> 00:14:22,990
And then let's say we just have four also.

290
00:14:22,990 --> 00:14:25,090
So let's say two is connected to four.

291
00:14:25,090 --> 00:14:28,990
Now if this is the graph which is given to us it should return true true right.

292
00:14:28,990 --> 00:14:30,430
Because there is no cycle.

293
00:14:30,430 --> 00:14:31,870
Again this is not a cycle.

294
00:14:31,870 --> 00:14:34,750
This is not a cycle because this is the direction from 0 to 1.

295
00:14:34,750 --> 00:14:36,340
And then we have this way.

296
00:14:36,340 --> 00:14:36,730
All right.

297
00:14:36,730 --> 00:14:38,080
So this should be possible.

298
00:14:38,080 --> 00:14:41,710
So let's go ahead and give this input and check whether our code is working.

299
00:14:41,710 --> 00:14:44,020
So in this case n is equal to five.

300
00:14:44,650 --> 00:14:48,700
And let's give let's create the prereq array.

301
00:14:48,700 --> 00:14:49,900
So prereqs array.

302
00:14:49,900 --> 00:14:52,720
So we have a link from 0 to 1.

303
00:14:52,720 --> 00:14:54,370
So let's write that.

304
00:14:54,370 --> 00:14:56,020
So we have one comma zero.

305
00:14:57,020 --> 00:14:59,330
Which means to do one, we have to do zero.

306
00:14:59,360 --> 00:15:00,320
Let's continue.

307
00:15:00,320 --> 00:15:03,710
Now we have this over here from 0 to 2.

308
00:15:03,740 --> 00:15:03,920
Right.

309
00:15:03,920 --> 00:15:06,050
So this means we have two comma zero.

310
00:15:07,820 --> 00:15:08,780
And.

311
00:15:09,390 --> 00:15:12,390
Then we have this link over here from 2 to 3.

312
00:15:12,420 --> 00:15:15,030
So this means three comma two.

313
00:15:17,100 --> 00:15:20,130
Then we have this link over here from 3 to 1.

314
00:15:20,130 --> 00:15:20,370
Right.

315
00:15:20,370 --> 00:15:22,440
So we have one comma three.

316
00:15:24,110 --> 00:15:27,410
And then we have this link over here from 2 to 4.

317
00:15:27,410 --> 00:15:29,390
So that means that's four comma two right.

318
00:15:29,390 --> 00:15:30,740
So that's four comma two.

319
00:15:30,770 --> 00:15:32,510
So 12345.

320
00:15:32,510 --> 00:15:34,700
And we have five elements over here.

321
00:15:35,120 --> 00:15:35,420
All right.

322
00:15:35,450 --> 00:15:39,890
Now let's go ahead and run our code and see what's the output that we are getting.

323
00:15:39,890 --> 00:15:40,430
Now.

324
00:15:40,430 --> 00:15:42,140
We are getting true which is correct.

325
00:15:42,140 --> 00:15:42,350
Right.

326
00:15:42,350 --> 00:15:43,340
So this is possible.

327
00:15:43,340 --> 00:15:44,270
So this is correct.

328
00:15:44,270 --> 00:15:48,500
Now let's just change the direction of this from 0 to 1.

329
00:15:48,500 --> 00:15:49,940
So let me just change this.

330
00:15:49,940 --> 00:15:51,350
So I'm taking a pen.

331
00:15:51,350 --> 00:15:52,820
Let's change this in this way.

332
00:15:52,820 --> 00:15:54,470
So from one 1 to 0.

333
00:15:54,470 --> 00:15:58,040
So over here if we have this in this direction there is a clear cycle.

334
00:15:58,040 --> 00:15:59,810
And this should return false.

335
00:15:59,810 --> 00:16:01,880
So let's go ahead and try this.

336
00:16:02,420 --> 00:16:05,480
So this one over here I'm just changing it to zero comma one.

337
00:16:08,060 --> 00:16:10,640
And let's run our code and we get false.

338
00:16:10,640 --> 00:16:12,110
So this is a cycle.

339
00:16:12,110 --> 00:16:14,660
So we have identified this and it's not possible.

340
00:16:14,660 --> 00:16:16,070
So yes our code is working.

341
00:16:16,070 --> 00:16:20,240
Now let's also take an example where we have an unconnected component.

342
00:16:20,240 --> 00:16:21,680
So I'm changing this back.

343
00:16:21,680 --> 00:16:21,950
All right.

344
00:16:21,950 --> 00:16:23,780
So I'm changing this back.

345
00:16:23,780 --> 00:16:25,550
So let's have.

346
00:16:27,310 --> 00:16:29,020
This in this direction itself.

347
00:16:29,020 --> 00:16:31,150
And over here, let's just have, um.

348
00:16:32,130 --> 00:16:32,820
Five.

349
00:16:33,430 --> 00:16:34,240
And six.

350
00:16:34,240 --> 00:16:35,410
So 6 to 5.

351
00:16:35,410 --> 00:16:38,500
And let's say we have seven also over here.

352
00:16:38,950 --> 00:16:43,360
So let's add this part also to our input and see whether it's working.

353
00:16:44,120 --> 00:16:46,850
So I'm changing this back to one comma zero.

354
00:16:50,530 --> 00:16:51,250
All right.

355
00:16:51,250 --> 00:16:54,310
Now over here n is equal to eight.

356
00:16:55,870 --> 00:16:57,820
And let's add these connections.

357
00:16:57,820 --> 00:17:00,430
So there is a connection from 6 to 5 right.

358
00:17:00,430 --> 00:17:02,110
So that's five comma six.

359
00:17:03,270 --> 00:17:05,730
And there is a connection from 5 to 7.

360
00:17:05,730 --> 00:17:08,010
So that is seven comma five.

361
00:17:09,000 --> 00:17:11,790
And there is a connection from 7 to 6.

362
00:17:11,790 --> 00:17:12,240
Right.

363
00:17:12,240 --> 00:17:14,370
So that's six comma seven.

364
00:17:14,370 --> 00:17:17,040
So this should give us the output as false.

365
00:17:17,040 --> 00:17:18,150
So let's try it.

366
00:17:18,690 --> 00:17:19,650
Yes that's false.

367
00:17:19,650 --> 00:17:21,810
It's identifying that there is a cycle over here.

368
00:17:21,810 --> 00:17:23,400
So yes our code is working.