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

2
00:00:01,620 --> 00:00:06,450
In this video, let's try to think how we can solve this question in a better manner.

3
00:00:06,450 --> 00:00:11,460
Now for this we will make use of the topo sort or topological sort.

4
00:00:11,490 --> 00:00:16,800
Now before we see how we can use this to solve this question with which we are dealing, let's first

5
00:00:16,800 --> 00:00:19,650
try to understand what is topological sort.

6
00:00:19,680 --> 00:00:23,820
Now topological sort is a linear ordering of vertices.

7
00:00:23,820 --> 00:00:30,750
So it's a linear ordering of vertices such that for every directed edge a to b, a appears before b

8
00:00:30,750 --> 00:00:31,650
in the ordering.

9
00:00:31,650 --> 00:00:33,720
So this is the definition of topological sort.

10
00:00:33,750 --> 00:00:36,030
Now let's take an example to understand this.

11
00:00:36,030 --> 00:00:38,010
So over here we have a graph.

12
00:00:38,010 --> 00:00:39,510
All right so it's a directed graph.

13
00:00:39,510 --> 00:00:46,230
Now an example of a topological sort for this particular graph would be 134265.

14
00:00:46,230 --> 00:00:49,500
Again remember this is just one possible topological sort.

15
00:00:49,500 --> 00:00:52,740
For the same graph we can have multiple topological sorts.

16
00:00:52,740 --> 00:00:55,020
Now let's try to read this definition again.

17
00:00:55,020 --> 00:00:56,520
So it's a linear ordering.

18
00:00:56,520 --> 00:00:58,740
So this is a linear ordering of the vertices.

19
00:00:58,740 --> 00:01:00,960
So these are the vertices in this graph.

20
00:01:00,960 --> 00:01:07,050
And then it's mentioned that for every directed edge a to b a appears before b in the ordering.

21
00:01:07,050 --> 00:01:08,640
Now let's take a few examples.

22
00:01:08,640 --> 00:01:11,610
So over here we have a directed edge from 1 to 2.

23
00:01:11,610 --> 00:01:14,850
Right now let's take a look at one and two in our ordering.

24
00:01:14,850 --> 00:01:17,520
And you can see that one appears before two.

25
00:01:17,550 --> 00:01:17,910
Right.

26
00:01:17,910 --> 00:01:21,210
And that is what is mentioned over here a has to appear before B.

27
00:01:21,210 --> 00:01:24,000
Let's take another example for example 4 to 5.

28
00:01:24,000 --> 00:01:29,820
So if we look at this you can see four is appearing before five in this linear ordering.

29
00:01:29,820 --> 00:01:32,640
So this is what we mean with topological sort.

30
00:01:32,670 --> 00:01:36,030
Now let's also try to understand what is the criteria.

31
00:01:36,030 --> 00:01:39,570
If topological sort can be applied for a particular graph.

32
00:01:39,570 --> 00:01:41,010
So there is a restriction.

33
00:01:41,370 --> 00:01:47,520
Now this type of a sort can be applied for a graph only if the graph is a Dag.

34
00:01:48,000 --> 00:01:51,900
And Dag stands for directed acyclic graph.

35
00:01:51,900 --> 00:01:52,170
All right.

36
00:01:52,170 --> 00:01:56,280
So it should be a directed graph because only then we have something like A to B.

37
00:01:56,280 --> 00:01:58,590
And then it should be acyclic in nature.

38
00:01:58,590 --> 00:02:01,350
Now let's try to understand why it should be acyclic.

39
00:02:01,350 --> 00:02:04,920
For example we have this graph over here which is cyclic in nature.

40
00:02:04,920 --> 00:02:05,190
Right.

41
00:02:05,190 --> 00:02:08,850
We have one going to two, two going to three and three going to one.

42
00:02:08,850 --> 00:02:14,850
Now we cannot order it in a linear manner such that A appears before B, because we don't know whether

43
00:02:14,850 --> 00:02:19,410
one appears before two or whether uh two appears before one.

44
00:02:19,410 --> 00:02:19,590
Right.

45
00:02:19,590 --> 00:02:22,230
For example, let's just write it as one, two, three.

46
00:02:22,230 --> 00:02:26,040
Now, if I write it like this, you can see one is appearing before three, right?

47
00:02:26,040 --> 00:02:29,130
But again over here you can see we have three, two, one.

48
00:02:29,130 --> 00:02:31,920
So we could say that three should appear before one.

49
00:02:31,920 --> 00:02:32,430
All right.

50
00:02:32,460 --> 00:02:36,870
Now if I write it as three one, two then three is appearing before one.

51
00:02:36,870 --> 00:02:39,240
And we have three appearing before two.

52
00:02:39,270 --> 00:02:41,700
But then over here you have two appearing before three.

53
00:02:41,700 --> 00:02:43,440
So this also cannot be done right.

54
00:02:55,980 --> 00:02:59,610
Now over here, we cannot say what comes before what.

55
00:02:59,610 --> 00:03:05,340
So that's why we cannot write it as a linear ordering of the pairs such that A appears before b.

56
00:03:05,340 --> 00:03:06,540
Now what do I mean with that?

57
00:03:06,540 --> 00:03:08,070
Let's write the possibilities right.

58
00:03:08,070 --> 00:03:09,360
We have one, two and three.

59
00:03:09,360 --> 00:03:11,400
So there is an edge from 1 to 2.

60
00:03:11,400 --> 00:03:13,110
So I could write one, two, three.

61
00:03:13,140 --> 00:03:15,120
Now we'll see why this cannot be done.

62
00:03:15,120 --> 00:03:17,070
Now let's try 231.

63
00:03:17,070 --> 00:03:18,360
So that's another possibility.

64
00:03:18,360 --> 00:03:19,110
231.

65
00:03:19,110 --> 00:03:21,180
And another possibility is 312.

66
00:03:21,180 --> 00:03:21,360
Right.

67
00:03:21,360 --> 00:03:22,200
312.

68
00:03:23,070 --> 00:03:26,340
Now I cannot write three, two, one because there is no connection over here, right?

69
00:03:26,340 --> 00:03:29,490
Similarly, I cannot write two, one, three or anything else.

70
00:03:29,490 --> 00:03:31,650
So these are the three possibilities, right?

71
00:03:31,650 --> 00:03:37,830
So if I start at one I can write one, two, three I could write 231 or I can write 312.

72
00:03:37,830 --> 00:03:40,230
Now let's take a look at why this is wrong.

73
00:03:40,230 --> 00:03:41,850
123 is it right.

74
00:03:41,850 --> 00:03:43,590
So we have a link from 1 to 2.

75
00:03:43,620 --> 00:03:46,500
So one is appearing before two we have a link from 2 to 3.

76
00:03:46,500 --> 00:03:48,240
So two is appearing before three.

77
00:03:48,240 --> 00:03:50,100
But then we have a link from 3 to 1.

78
00:03:50,100 --> 00:03:52,050
So three should be appearing before one.

79
00:03:52,050 --> 00:03:53,010
So this is wrong right.

80
00:03:53,010 --> 00:03:55,950
So this this this is not satisfying this condition.

81
00:03:55,950 --> 00:03:57,240
What about 231.

82
00:03:57,240 --> 00:03:59,070
So we have a link from 2 to 3.

83
00:03:59,070 --> 00:03:59,940
So this is fine.

84
00:03:59,940 --> 00:04:01,200
We have a link from 3 to 1.

85
00:04:01,200 --> 00:04:02,010
So this is fine.

86
00:04:02,010 --> 00:04:03,750
But then we have a link from 1 to 2.

87
00:04:03,780 --> 00:04:05,310
So one should come before two.

88
00:04:05,340 --> 00:04:06,360
So this is also wrong.

89
00:04:06,360 --> 00:04:09,570
Similarly over here we have three one and one two which is fine.

90
00:04:09,570 --> 00:04:10,740
But then we have two three.

91
00:04:10,740 --> 00:04:12,450
So two should be appearing before three.

92
00:04:12,450 --> 00:04:13,740
So this is also wrong.

93
00:04:13,740 --> 00:04:19,830
So that's why if the graph is cyclic in nature then we cannot write a topological sort for that particular

94
00:04:19,830 --> 00:04:20,220
graph.

95
00:04:20,220 --> 00:04:21,810
So this is an interesting observation.

96
00:04:21,810 --> 00:04:26,520
So we can have the topological sort only for a directed acyclic graph.

97
00:04:26,520 --> 00:04:26,940
All right.

98
00:04:26,970 --> 00:04:28,320
Now let's proceed.

99
00:04:29,200 --> 00:04:34,030
And let's try to think how we can use this topological sort.

100
00:04:34,060 --> 00:04:35,350
Let's let's see two things.

101
00:04:35,350 --> 00:04:40,030
Actually let's try to see how we can do the do a topological sort.

102
00:04:40,030 --> 00:04:43,420
And let's also see how we can use it for our question.

103
00:04:43,420 --> 00:04:46,330
So these are the two things that we are trying to think about now.

104
00:04:46,330 --> 00:04:48,370
So again we have our example over here.

105
00:04:48,370 --> 00:04:51,790
Now first let's see how we do a topological sort.

106
00:04:51,820 --> 00:04:56,710
Now for this we will calculate the indegree factor for every node.

107
00:04:56,710 --> 00:04:58,060
Now for every vertex.

108
00:04:58,060 --> 00:04:59,950
So what is the indegree factor.

109
00:04:59,950 --> 00:05:06,940
The indegree factor for a particular vertex is the number of edges pointing into that particular vertex.

110
00:05:06,940 --> 00:05:11,950
For example, for this vertex over here, there is no edge pointing into it, right?

111
00:05:11,950 --> 00:05:16,690
So we can say that the indegree factor for this node over here is equal to zero.

112
00:05:16,690 --> 00:05:17,200
All right.

113
00:05:17,230 --> 00:05:21,520
Now what about this node over here you can see there are two edges pointing into it.

114
00:05:21,520 --> 00:05:21,820
Right.

115
00:05:21,820 --> 00:05:25,150
So we can say that the indegree factor for this is equal to two.

116
00:05:25,180 --> 00:05:28,150
Similarly for three the indegree factor is equal to zero.

117
00:05:28,150 --> 00:05:31,240
For six we have one edge pointing into it.

118
00:05:31,240 --> 00:05:33,190
So the indegree factor is equal to one.

119
00:05:33,190 --> 00:05:36,220
For five we have three edges pointing into it.

120
00:05:36,220 --> 00:05:40,870
So the indegree factor is equal to three, and for four we have one edge pointing into it.

121
00:05:40,870 --> 00:05:42,850
So the indegree factor is equal to one.

122
00:05:42,850 --> 00:05:43,330
All right.

123
00:05:43,330 --> 00:05:46,630
Now after finding the indegree factor for every vertex.

124
00:05:46,630 --> 00:05:49,900
And again we are dealing with how we can implement the topological sort.

125
00:05:49,900 --> 00:05:53,170
So first we find the indegree factor for the vertices.

126
00:05:53,170 --> 00:05:57,220
Then we will just take any vertex with indegree equal to zero.

127
00:05:57,220 --> 00:05:59,920
Now over here for example we take vertex one.

128
00:05:59,920 --> 00:06:02,740
So vertex one has an indegree factor equal to zero.

129
00:06:02,740 --> 00:06:04,960
And then we disregard this vertex.

130
00:06:04,960 --> 00:06:08,800
So that means that for every connection from it right.

131
00:06:08,800 --> 00:06:11,710
So there is a connection from 1 to 4 and from 1 to 2.

132
00:06:11,740 --> 00:06:16,930
So for these two because we have removed this we have to decrement the indegree factor by one.

133
00:06:16,930 --> 00:06:21,310
So one minus one we get zero over here and two minus one we get one over here.

134
00:06:21,310 --> 00:06:23,350
So the indegree factor over here is now one.

135
00:06:23,350 --> 00:06:25,270
And over here is equal to zero.

136
00:06:25,690 --> 00:06:29,860
Now we again take another vertex with indegree factor equal to zero.

137
00:06:29,860 --> 00:06:33,730
So we can see that this node four has an integrity factor zero.

138
00:06:33,730 --> 00:06:36,640
So let's take this out and we remove it.

139
00:06:36,640 --> 00:06:36,910
All right.

140
00:06:36,910 --> 00:06:38,380
So we consider this is removed.

141
00:06:38,380 --> 00:06:41,860
So that means we are going to decrement its connections by one.

142
00:06:41,860 --> 00:06:44,260
So this is having a connection from 4 to 5.

143
00:06:44,260 --> 00:06:46,930
So there is an edge pointing into five from four.

144
00:06:46,930 --> 00:06:50,440
So we are going to decrement the indegree factor of five by one.

145
00:06:50,440 --> 00:06:51,790
And we get two over here.

146
00:06:51,790 --> 00:06:52,240
All right.

147
00:06:52,240 --> 00:06:53,500
Now again we continue.

148
00:06:53,500 --> 00:06:56,440
We take another vertex with indegree factor zero.

149
00:06:56,440 --> 00:06:59,230
So we can see that three has an indegree factor zero.

150
00:06:59,230 --> 00:07:02,980
So let's take it out and we decrement these three by one.

151
00:07:02,980 --> 00:07:04,570
So over here we get zero.

152
00:07:04,570 --> 00:07:07,090
We get zero over here and we get one over here.

153
00:07:07,090 --> 00:07:10,510
Now again we take another vertex with indegree factor zero.

154
00:07:10,510 --> 00:07:12,340
So we could take any one among these two.

155
00:07:12,370 --> 00:07:14,050
So let's go ahead and take two.

156
00:07:14,050 --> 00:07:15,490
And this is removed.

157
00:07:15,490 --> 00:07:17,650
Now there is nothing to reduce right.

158
00:07:17,650 --> 00:07:23,410
So there is no edge which is proceeding out of vertex two to any other vertex.

159
00:07:23,410 --> 00:07:23,590
Right.

160
00:07:23,590 --> 00:07:25,120
So there is nothing to reduce.

161
00:07:25,120 --> 00:07:27,040
Again we go ahead and take out six.

162
00:07:27,040 --> 00:07:31,540
And at this point we reduce the indegree factor of this vertex over here.

163
00:07:31,540 --> 00:07:33,100
And this also becomes zero.

164
00:07:33,100 --> 00:07:35,020
And then we go ahead and take this out.

165
00:07:35,020 --> 00:07:42,250
So 143265 is one possible topological sort of this graph which was given to us.

166
00:07:42,250 --> 00:07:46,510
So again this is how we go ahead and implement the topological sort.

167
00:07:46,540 --> 00:07:48,940
Now let's try to see whether this is valid.

168
00:07:48,940 --> 00:07:51,820
For example we have this connection from 1 to 2.

169
00:07:51,820 --> 00:07:57,190
And you can see that one is appearing before two which is the definition of the proper sort or topological

170
00:07:57,190 --> 00:07:57,430
sort.

171
00:07:57,430 --> 00:07:59,860
So yes, this is a valid topological sort.

172
00:07:59,860 --> 00:08:01,420
So this is true for any connection.

173
00:08:01,420 --> 00:08:03,970
For example you take the connection from 6 to 5.

174
00:08:03,970 --> 00:08:08,590
So you have six before five or you have 4 to 5 and you have four before five, etc..

175
00:08:08,590 --> 00:08:09,220
All right.

176
00:08:09,220 --> 00:08:12,460
So we have seen how to implement the topological sort.

177
00:08:12,490 --> 00:08:18,880
Now let's try to think about how we can tweak this and use this to solve our question.

178
00:08:18,880 --> 00:08:26,470
Now if the graph which is given to us, if we implement the topological sort on that graph, then once

179
00:08:26,470 --> 00:08:32,830
we do that, if we can check whether every vertex was reached and if every vertex was reached, for

180
00:08:32,830 --> 00:08:35,470
example, in this case we got every vertex over here.

181
00:08:35,470 --> 00:08:35,830
Right?

182
00:08:35,830 --> 00:08:41,800
That means that the graph over here is acyclic or it does not have a cycle.

183
00:08:41,800 --> 00:08:46,840
Again, in the question, we are actually checking whether the graph which is given to us has a cycle

184
00:08:46,840 --> 00:08:47,260
or not.

185
00:08:47,260 --> 00:08:48,370
So that is what we are checking.

186
00:08:48,370 --> 00:08:51,940
Now let's take another example and let's try to understand why this helps.

187
00:08:51,940 --> 00:08:55,870
So over here we have another example where there is a cycle.

188
00:08:55,870 --> 00:08:59,170
So there is a cycle over here right now again let's find the indegree factor.

189
00:08:59,170 --> 00:09:02,170
So over here it's 021 and one.

190
00:09:02,170 --> 00:09:03,700
So nothing comes in over here.

191
00:09:03,700 --> 00:09:04,360
So it's zero.

192
00:09:04,360 --> 00:09:08,170
And again you have one and two two edges coming into this vertex.

193
00:09:08,170 --> 00:09:10,270
So that's why the indegree factor over here is two.

194
00:09:10,270 --> 00:09:13,300
And then you have one edge coming into this edge this vertex.

195
00:09:13,300 --> 00:09:15,190
So the indegree factor over here is one.

196
00:09:15,190 --> 00:09:18,730
And then again because this edge is coming into this vertex.

197
00:09:18,730 --> 00:09:21,370
So the indegree factor over here is also equal to one.

198
00:09:21,370 --> 00:09:25,420
Now let's take out let's proceed with the same method that we discussed over here.

199
00:09:25,420 --> 00:09:28,510
We take out this because only this has an indegree factor.

200
00:09:28,950 --> 00:09:32,490
So we take this out and we decrement this by one.

201
00:09:32,490 --> 00:09:34,890
So we have the integral factor over here also one.

202
00:09:34,890 --> 00:09:39,270
And we can see in all these places the integral factor now is equal to one.

203
00:09:39,270 --> 00:09:40,920
And there is nothing with zero right.

204
00:09:40,920 --> 00:09:43,410
So we cannot proceed and we cannot take it out.

205
00:09:43,410 --> 00:09:43,560
Right.

206
00:09:43,560 --> 00:09:49,530
So you can see that once we implement proper sort on this graph, we are not getting all the vertexes

207
00:09:49,530 --> 00:09:49,740
right.

208
00:09:49,740 --> 00:09:53,010
We just got one vertex and we are not getting all the vertices.

209
00:09:53,010 --> 00:09:57,720
And that is because we were not able to proceed, because at this point there is nothing with Indegree

210
00:09:57,720 --> 00:09:58,500
equal to zero.

211
00:09:58,500 --> 00:10:00,480
And this is because of this cycle.

212
00:10:00,480 --> 00:10:04,500
So how do we use the topo sort algorithm to solve this question?

213
00:10:04,500 --> 00:10:08,370
We are going to implement the topo sort on the graph which is given to us.

214
00:10:08,370 --> 00:10:14,910
And after doing that, if there is no cycle, then we would have reached all the vertices.

215
00:10:14,910 --> 00:10:20,790
And if there is a cycle, then the count of vertices that we are reaching is not going to be equal to

216
00:10:20,790 --> 00:10:22,050
the number of vertices.

217
00:10:22,050 --> 00:10:24,510
So this is how we are going to solve this question.

218
00:10:24,510 --> 00:10:27,300
And now let's try to think about how to implement this.

219
00:10:27,300 --> 00:10:29,430
So again we have our graph over here.

220
00:10:29,430 --> 00:10:33,660
We have already discussed the intuition and the method by which we will implement this.

221
00:10:33,660 --> 00:10:38,490
Now let's go ahead and write and think about the pseudocode for this implementation of this algorithm.

222
00:10:38,490 --> 00:10:40,620
So first this graph is given to us.

223
00:10:41,040 --> 00:10:43,170
And for this graph we are given n.

224
00:10:43,170 --> 00:10:45,330
In this case n is going to be equal to six.

225
00:10:45,330 --> 00:10:48,510
And then we will be given the prerequisites array.

226
00:10:48,510 --> 00:10:48,870
All right.

227
00:10:48,900 --> 00:10:53,850
Now using n and the prerequisites array we will just loop through the prerequisites array.

228
00:10:53,850 --> 00:10:56,550
And then we will create our adjacency list.

229
00:10:56,550 --> 00:10:58,500
So this is going to be our first step.

230
00:10:58,500 --> 00:11:02,040
And then we will also find the indegree factor for every node.

231
00:11:02,040 --> 00:11:02,370
Right.

232
00:11:02,370 --> 00:11:05,340
So again we will use the prerequisites array for that.

233
00:11:05,340 --> 00:11:10,260
So if this is the graph which is given to us, the actual input for the question would be this array

234
00:11:10,260 --> 00:11:10,560
over here.

235
00:11:10,560 --> 00:11:10,830
Right.

236
00:11:10,830 --> 00:11:16,620
So we have four comma one which means that before doing four we have to complete one which is this link

237
00:11:16,620 --> 00:11:17,040
over here.

238
00:11:17,040 --> 00:11:20,730
Similarly two comma one indicates before doing two we have to do one.

239
00:11:20,730 --> 00:11:21,990
Two comma three indicates.

240
00:11:21,990 --> 00:11:24,120
Before doing two we have to do three, etc..

241
00:11:24,120 --> 00:11:27,090
So this array over here can be visualized like this.

242
00:11:27,090 --> 00:11:33,300
Now we can just calculate the adjacency list and the indegree factor using the prerequisites array and

243
00:11:33,300 --> 00:11:33,600
n.

244
00:11:33,600 --> 00:11:35,970
So in this case n will be equal to six.

245
00:11:35,970 --> 00:11:39,060
So that's why the vertices are from 0 to 5.

246
00:11:39,060 --> 00:11:39,480
All right.

247
00:11:39,510 --> 00:11:42,000
Now let's have our adjacency list over here.

248
00:11:42,150 --> 00:11:42,630
All right.

249
00:11:42,630 --> 00:11:46,710
So initially it's going to be an empty array an array with empty arrays.

250
00:11:46,710 --> 00:11:46,920
Right.

251
00:11:46,920 --> 00:11:49,350
So it's going to have six empty arrays.

252
00:11:49,350 --> 00:11:52,500
So this is 01234 and five.

253
00:11:52,500 --> 00:11:54,540
So which represents these five nodes.

254
00:11:54,540 --> 00:11:57,480
So let's write the indices over here 0 to 5.

255
00:11:57,480 --> 00:12:03,390
And then we are going to have our indegree array which is also going to have five elements.

256
00:12:03,390 --> 00:12:07,560
And initially we are just going to fill zero for each index.

257
00:12:07,560 --> 00:12:07,920
All right.

258
00:12:07,920 --> 00:12:10,140
So we're just going to initialize it in this manner.

259
00:12:10,140 --> 00:12:15,600
Now we will loop through our prerequisites array and we will fill our adjacency list.

260
00:12:15,600 --> 00:12:17,340
So let's go ahead and do that.

261
00:12:18,960 --> 00:12:20,670
All right, so how do we fill this?

262
00:12:20,700 --> 00:12:23,640
We can see that there is a link from 0 to 5.

263
00:12:23,640 --> 00:12:25,050
So that's why we have five over here.

264
00:12:25,050 --> 00:12:27,210
And there is a link from 1 to 4 and two.

265
00:12:27,240 --> 00:12:28,770
So we have four and two over here.

266
00:12:28,770 --> 00:12:31,650
Now there is a there is no link going out from two.

267
00:12:31,680 --> 00:12:35,520
So this is empty now from three we have two five and zero.

268
00:12:35,520 --> 00:12:37,080
So 250 are there over here.

269
00:12:37,080 --> 00:12:38,640
And then from four we have five.

270
00:12:38,640 --> 00:12:39,870
So that's why we have five over here.

271
00:12:39,870 --> 00:12:41,610
And then from five nothing goes out.

272
00:12:41,610 --> 00:12:44,340
So this is how we build our adjacency list.

273
00:12:44,340 --> 00:12:49,170
Now let's think about how to get the indegree factors for each of these nodes right.

274
00:12:49,170 --> 00:12:52,470
Again we are just looping through the prerequisites array over here.

275
00:12:52,470 --> 00:12:54,930
Now we can see that we have four comma one.

276
00:12:54,930 --> 00:12:59,190
So this means that we have something coming in to four from one right.

277
00:12:59,190 --> 00:13:00,180
So that means this link.

278
00:13:00,180 --> 00:13:02,400
So before doing four we have to do one.

279
00:13:02,400 --> 00:13:07,140
Or we can visualize it in this manner which is an edge which is coming into four.

280
00:13:07,140 --> 00:13:10,560
So because we have four over here we are going to increment this by one.

281
00:13:10,560 --> 00:13:11,850
So we get one over here.

282
00:13:12,330 --> 00:13:14,640
Similarly over here we have two right.

283
00:13:14,640 --> 00:13:16,770
So we are going to increment two by one.

284
00:13:17,160 --> 00:13:18,900
And then over here again we have two.

285
00:13:18,930 --> 00:13:20,850
So let's increment this again by one.

286
00:13:20,850 --> 00:13:22,020
So we get two over here.

287
00:13:22,020 --> 00:13:23,580
And we have five over here.

288
00:13:23,580 --> 00:13:26,520
So we are going to increment the indegree factor of five by one.

289
00:13:26,520 --> 00:13:27,900
And then we have five over here.

290
00:13:27,900 --> 00:13:30,540
So let's again increment the indegree factor by one more.

291
00:13:30,540 --> 00:13:31,560
So we have two over here.

292
00:13:31,560 --> 00:13:32,550
Again we have five.

293
00:13:32,550 --> 00:13:34,140
So we increment it once more.

294
00:13:34,140 --> 00:13:35,280
We get three over here.

295
00:13:35,280 --> 00:13:36,720
And then we have zero over here.

296
00:13:36,720 --> 00:13:39,510
So we increment the indegree factor of this to one.

297
00:13:39,510 --> 00:13:44,280
So now we have our indegree array and we have our adjacency list.

298
00:13:44,280 --> 00:13:46,650
So this is going to be our first step.

299
00:13:46,650 --> 00:13:47,310
All right.

300
00:13:47,760 --> 00:13:52,920
Now we're just going to apply the topological sort algorithm which we discussed.

301
00:13:52,920 --> 00:13:57,000
So first we take any vertex which has an indegree factor of zero.

302
00:13:57,000 --> 00:14:00,570
So over here there are two vertices which have an indegree factor of zero.

303
00:14:00,570 --> 00:14:02,220
So we can take any one of these right.

304
00:14:02,220 --> 00:14:04,410
So let's take one for example.

305
00:14:04,470 --> 00:14:11,100
Now when we take out one over here in the adjacency list we can see that its connections are to four

306
00:14:11,100 --> 00:14:11,520
and two.

307
00:14:11,520 --> 00:14:11,820
Right.

308
00:14:11,820 --> 00:14:16,440
So for four and two we will reduce the indegree by one which are these two.

309
00:14:16,440 --> 00:14:16,740
Right.

310
00:14:16,740 --> 00:14:18,900
Because we are just removing this connection.

311
00:14:18,900 --> 00:14:22,710
So we have to reduce the indegree factor for four and two by one.

312
00:14:22,710 --> 00:14:23,640
So let's do that.

313
00:14:23,640 --> 00:14:26,520
So four just has one and two just has two right.

314
00:14:26,520 --> 00:14:27,900
So let's reduce one.

315
00:14:27,900 --> 00:14:29,190
So over here this we have zero.

316
00:14:29,190 --> 00:14:32,190
And over here we have two minus one which is equal to one.

317
00:14:32,190 --> 00:14:32,610
All right.

318
00:14:32,640 --> 00:14:33,690
Now we proceed.

319
00:14:33,690 --> 00:14:35,370
So we have already taken out one.

320
00:14:35,370 --> 00:14:41,340
Right now we take the next node which has an indegree factor of zero which is in this case we can take

321
00:14:41,340 --> 00:14:42,330
3 or 4.

322
00:14:42,330 --> 00:14:43,650
So let's just take four.

323
00:14:43,650 --> 00:14:47,490
And we reduce the indegree factor of its connection.

324
00:14:47,490 --> 00:14:49,740
So from four there is a connection of five.

325
00:14:49,740 --> 00:14:51,060
So we can see that over here.

326
00:14:51,060 --> 00:14:53,100
So we reduce this 3 to 2.

327
00:14:53,100 --> 00:14:53,640
All right.

328
00:14:54,060 --> 00:14:59,250
Now we again continue and take out the next node which has an indegree factor of zero.

329
00:14:59,250 --> 00:14:59,670
All right.

330
00:14:59,670 --> 00:15:01,440
So we have taken out one and four.

331
00:15:01,440 --> 00:15:03,510
And three has an indegree factor of zero.

332
00:15:03,510 --> 00:15:04,770
So let's take out three.

333
00:15:04,770 --> 00:15:08,610
And the neighbors the edges from three are two five and zero.

334
00:15:08,610 --> 00:15:12,000
So there is a connection going out from 3 to 2 five and zero.

335
00:15:12,000 --> 00:15:16,590
So for two five and zero we will reduce the indegree factor by one right.

336
00:15:16,590 --> 00:15:17,700
So we are doing that.

337
00:15:17,700 --> 00:15:20,700
So for two we are getting one minus one which is zero.

338
00:15:20,700 --> 00:15:23,160
For five we are getting two minus one which is one.

339
00:15:23,160 --> 00:15:26,670
And for zero we are getting one minus one which is equal to zero.

340
00:15:26,670 --> 00:15:27,150
All right.

341
00:15:27,150 --> 00:15:28,860
So we have taken out three.

342
00:15:28,860 --> 00:15:33,840
Now again let's continue and take out an element which has an indegree factor of zero which is among

343
00:15:33,840 --> 00:15:34,530
zero and two.

344
00:15:34,530 --> 00:15:35,580
We can take out any one.

345
00:15:35,580 --> 00:15:36,930
So let's take out zero.

346
00:15:36,930 --> 00:15:41,490
So if we take out zero we are going to decrement the indegree factor for five.

347
00:15:41,490 --> 00:15:42,900
So this becomes also zero.

348
00:15:42,900 --> 00:15:45,930
Now we have taken out zero and we are left with two and five.

349
00:15:45,930 --> 00:15:48,360
And both of them have an indegree factor of zero.

350
00:15:48,360 --> 00:15:50,250
So we can take out any one.

351
00:15:50,250 --> 00:15:52,860
So we take out two and there is nothing to reduce.

352
00:15:52,860 --> 00:15:54,600
You can see that again here.

353
00:15:54,600 --> 00:15:56,400
It's empty so there is nothing to reduce.

354
00:15:56,400 --> 00:15:58,200
And then we take the next one which is five.

355
00:15:58,200 --> 00:16:00,480
And this is our topological sort.

356
00:16:00,510 --> 00:16:07,170
Now once we apply the proper sort algorithm let's just count how many vertices we were able to visit.

357
00:16:07,170 --> 00:16:09,810
You can see that 123456.

358
00:16:09,810 --> 00:16:12,570
We were able to visit all the six vertices.

359
00:16:12,570 --> 00:16:15,240
And n in this case also is equal to six right.

360
00:16:15,240 --> 00:16:16,380
Which is 0 to 5.

361
00:16:16,380 --> 00:16:21,270
So because the count is equal to n, we were able to visit all the vertices.

362
00:16:21,270 --> 00:16:26,100
And that's why we can be sure that there is no cycle in the given graph.

363
00:16:26,100 --> 00:16:30,900
If there was a cycle, then the count over here would have been less than six.

364
00:16:30,900 --> 00:16:33,270
So this is how we are going to solve this question.

365
00:16:33,270 --> 00:16:36,090
Now let's go ahead and write the remaining part of the pseudocode.

366
00:16:36,090 --> 00:16:40,770
So the first step is we find the we create the adjacency list and the indegree factor array.

367
00:16:40,860 --> 00:16:46,440
Now secondly we are going to take the vertices with indegree equal to zero.

368
00:16:46,440 --> 00:16:48,750
And we will just push it to a stack.

369
00:16:48,750 --> 00:16:49,170
All right.

370
00:16:49,170 --> 00:16:51,390
Now we are going to have a while loop.

371
00:16:51,390 --> 00:16:55,470
And this will loop as long as something is there in our stack.

372
00:16:55,470 --> 00:16:59,340
Now once inside the while loop we will pop from the stack.

373
00:16:59,340 --> 00:16:59,760
All right.

374
00:16:59,760 --> 00:17:01,440
And then we will increment the count.

375
00:17:01,440 --> 00:17:04,350
So whenever we pop from the stack we will increment the count.

376
00:17:04,350 --> 00:17:06,930
So initially the count is going to be equal to zero.

377
00:17:07,110 --> 00:17:12,960
And when we have one element inside it and we come inside for example, and then we pop at that time

378
00:17:12,960 --> 00:17:14,340
count will be incremented to one.

379
00:17:14,340 --> 00:17:15,420
And this goes on like that.

380
00:17:15,420 --> 00:17:18,270
So we will trace this and take a look at it now.

381
00:17:18,520 --> 00:17:24,490
After incrementing the count, what we will do is we will decrement the indegree factor for its neighbors

382
00:17:24,490 --> 00:17:25,750
like we have seen over here, right?

383
00:17:25,750 --> 00:17:31,570
For example, when we take out one, when we took out one, then we checked its neighbors, which is

384
00:17:31,570 --> 00:17:35,920
four and two, and for four and two we decremented the indegree factor.

385
00:17:35,920 --> 00:17:38,350
So the same thing is something that we are going to do over here.

386
00:17:38,350 --> 00:17:44,620
So we will pop from the stack, we will increment the count and for its neighbors or for edges from

387
00:17:44,620 --> 00:17:45,970
that node to the other nodes.

388
00:17:45,970 --> 00:17:46,270
Right.

389
00:17:46,270 --> 00:17:49,420
For those the edges coming into it, right for these neighbors.

390
00:17:49,420 --> 00:17:54,430
So that's why for four and two, for example, over here we are going to decrement the indegree factor.

391
00:17:54,430 --> 00:17:56,650
After decrementing the indegree factor.

392
00:17:56,650 --> 00:18:02,560
We will check if the indegree factor for any of these nodes became zero, and if it became zero, we

393
00:18:02,560 --> 00:18:04,030
will push it to our stack.

394
00:18:04,030 --> 00:18:05,980
So this is going to be our pseudo code.

395
00:18:05,980 --> 00:18:06,400
All right.

396
00:18:06,400 --> 00:18:09,700
So if we have something we will push into the stack.

397
00:18:09,700 --> 00:18:12,400
And then we will again check if there is something in our stack.

398
00:18:12,400 --> 00:18:13,930
And then this goes on like that.

399
00:18:13,930 --> 00:18:14,290
All right.

400
00:18:14,290 --> 00:18:15,970
So this is how our code works.

401
00:18:15,970 --> 00:18:19,030
Now if there is a cycle for example let's take an example.

402
00:18:19,030 --> 00:18:20,860
Let's take a very simple example.

403
00:18:20,860 --> 00:18:22,930
Let's say one and zero.

404
00:18:22,930 --> 00:18:24,610
And then we have two.

405
00:18:25,210 --> 00:18:26,800
And there is a clear cycle over here.

406
00:18:26,800 --> 00:18:31,030
Now in this case n will be equal to three right n is equal to three.

407
00:18:31,030 --> 00:18:33,400
So let's try to understand what would happen.

408
00:18:33,400 --> 00:18:36,040
Let's again draw our adjacency list over here.

409
00:18:36,490 --> 00:18:40,900
Now for zero there is only one edge going out of it.

410
00:18:40,900 --> 00:18:42,310
So we would have two over here.

411
00:18:42,310 --> 00:18:46,420
And then for one there is one going out which is to zero.

412
00:18:46,420 --> 00:18:46,840
All right.

413
00:18:46,840 --> 00:18:49,900
And then for two there is one edge going out from it to one.

414
00:18:49,900 --> 00:18:53,500
So this is how our adjacency list would look like for this graph.

415
00:18:53,500 --> 00:18:55,690
And then what would be the indegree factor.

416
00:18:55,690 --> 00:18:56,830
Let's just write it over here.

417
00:18:56,830 --> 00:18:59,800
For one the indegree factor is one for zero.

418
00:18:59,830 --> 00:19:01,360
The indegree factor is one.

419
00:19:01,360 --> 00:19:03,970
And then for two the Indegree factor is one.

420
00:19:03,970 --> 00:19:04,300
All right.

421
00:19:04,330 --> 00:19:07,810
Now if we go ahead and look at our code.

422
00:19:07,810 --> 00:19:08,200
All right.

423
00:19:08,200 --> 00:19:13,630
So just so that our code works, let's just uh okay, let's just continue and then we'll see why it

424
00:19:13,630 --> 00:19:14,650
will stop immediately.

425
00:19:14,650 --> 00:19:19,180
So at this point when we come to this step, we will see that there is nothing with indegree factor

426
00:19:19,180 --> 00:19:19,450
zero.

427
00:19:19,450 --> 00:19:19,720
Right.

428
00:19:19,720 --> 00:19:24,040
So it will not even come inside and count is initialized to zero.

429
00:19:24,040 --> 00:19:28,690
So when we come out, we will check whether count is equal to the number of vertices, which is three

430
00:19:28,690 --> 00:19:30,190
and zero is not equal to three.

431
00:19:30,190 --> 00:19:32,320
So we can be sure that there is a cycle.

432
00:19:32,320 --> 00:19:35,440
And we know that we cannot complete the courses.

433
00:19:35,440 --> 00:19:37,630
Now let's say n was equal to four.

434
00:19:37,630 --> 00:19:38,020
All right.

435
00:19:38,020 --> 00:19:39,520
So let's say n was equal to four.

436
00:19:39,520 --> 00:19:42,850
And there is a vertex for over here which is not connected to anything.

437
00:19:42,850 --> 00:19:45,520
So there is an indegree factor over here which is equal to zero.

438
00:19:45,520 --> 00:19:45,880
All right.

439
00:19:45,880 --> 00:19:47,440
So let's just have that also.

440
00:19:47,440 --> 00:19:50,230
So at index four this is going to be index four.

441
00:19:50,260 --> 00:19:51,010
There is nothing.

442
00:19:51,010 --> 00:19:55,210
So again this part over here is going to be an empty array in our adjacency list.

443
00:19:55,210 --> 00:19:59,530
Now what will happen is again we create our adjacency list and indegree factor array.

444
00:19:59,530 --> 00:20:02,110
And then we will just push four to our stack.

445
00:20:02,110 --> 00:20:03,730
We will come inside the while loop.

446
00:20:03,730 --> 00:20:06,700
We will pop and count will change from 0 to 1.

447
00:20:06,700 --> 00:20:08,830
And then we will decrement its neighbor.

448
00:20:08,830 --> 00:20:10,360
So there is nothing to decrement.

449
00:20:10,360 --> 00:20:15,040
And then we will check if there is something which can be pushed to the stack if its indegree is equal

450
00:20:15,040 --> 00:20:15,400
to zero.

451
00:20:15,400 --> 00:20:15,640
Right.

452
00:20:15,640 --> 00:20:18,160
So we see nothing has an indegree factor of zero.

453
00:20:18,160 --> 00:20:22,960
And then when we come over here we would we would not again go into the loop and we will come out right.

454
00:20:22,960 --> 00:20:25,090
So again we can see count is equal to one.

455
00:20:25,090 --> 00:20:27,130
And n in this case is equal to four.

456
00:20:27,130 --> 00:20:31,750
So you can see we have seen a case where the count over here became equal to n right.

457
00:20:31,750 --> 00:20:35,470
That was because all the vertices were visited.

458
00:20:35,470 --> 00:20:38,080
And that happened because there is no cycle.

459
00:20:38,080 --> 00:20:40,750
So this is how we are going to solve this question.

460
00:20:40,750 --> 00:20:46,840
We will just implement the topple sort algorithm, and we will have a count to track how many vertices

461
00:20:46,840 --> 00:20:52,930
where we were able to visit, or how many vertices by implementing the topple sort got an indegree factor

462
00:20:52,930 --> 00:20:54,160
of zero at some point.

463
00:20:54,160 --> 00:20:58,960
Now, if the count is equal to the number of vertices, then we can be sure there is no cycle.

464
00:20:58,960 --> 00:21:04,330
And if the count is not equal to the number of vertices, then there is a cycle, and hence we cannot

465
00:21:04,330 --> 00:21:05,680
complete all the questions.

466
00:21:05,680 --> 00:21:07,690
And this is how we can solve this question.

467
00:21:07,690 --> 00:21:11,710
Now let's take a quick look at the complexity analysis of this solution.

468
00:21:11,710 --> 00:21:18,760
The time complexity of this solution is going to be of the order of p plus n plus e, where p is the

469
00:21:18,760 --> 00:21:24,520
number of elements in the prerequisites array, and n is the number of vertices, and e is the number

470
00:21:24,520 --> 00:21:25,120
of edges.

471
00:21:25,120 --> 00:21:27,370
So let's try to understand why this is so.

472
00:21:27,370 --> 00:21:32,230
And again you can notice this is much better than the previous time complexity which we got with the

473
00:21:32,230 --> 00:21:33,100
brute force method.

474
00:21:33,100 --> 00:21:35,410
Now let's try to understand this time complexity.

475
00:21:35,440 --> 00:21:37,660
Now what are the things that take up time.

476
00:21:37,660 --> 00:21:41,170
First of all we are going to form this adjacency list and indegree factor right.

477
00:21:41,170 --> 00:21:42,880
So this will take some operations.

478
00:21:42,880 --> 00:21:47,470
Now to form the adjacency list we will have to do p plus n operations right.

479
00:21:47,470 --> 00:21:51,970
Because initially we will have to create an array with an empty arrays.

480
00:21:51,970 --> 00:21:54,130
So that's why we have n operations over here.

481
00:21:54,130 --> 00:21:56,890
Then we have to loop through the prerequisites array.

482
00:21:56,920 --> 00:21:59,140
So that's why we have p operations over here.

483
00:21:59,140 --> 00:22:02,200
And then fill the edges into the adjacency list.

484
00:22:02,200 --> 00:22:06,190
So that's why to form the adjacency list we'll have to do p plus n operations.

485
00:22:06,190 --> 00:22:11,980
And to get the indegree factor again right we have to go through the p uh prerequisites.

486
00:22:11,980 --> 00:22:13,240
So we have to loop through them.

487
00:22:13,240 --> 00:22:17,590
And again we have to initially form an array which is empty right.

488
00:22:17,590 --> 00:22:18,160
Or and then we have.

489
00:22:18,330 --> 00:22:23,760
To fill each of the places and places in that array with zero, and then we loop through the prerequisites

490
00:22:23,760 --> 00:22:26,250
array and find the indegree factor for each vertex.

491
00:22:26,250 --> 00:22:28,950
So over here also we are going to do p plus n operations.

492
00:22:28,950 --> 00:22:36,420
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.

493
00:22:36,420 --> 00:22:36,810
All right.

494
00:22:36,840 --> 00:22:38,520
Now what else takes up time.

495
00:22:38,520 --> 00:22:42,360
So this part over here let's take a look at this part over here.

496
00:22:42,360 --> 00:22:45,960
Also we are going to do a total of N plus E operations.

497
00:22:45,960 --> 00:22:46,590
Why is that.

498
00:22:46,590 --> 00:22:48,840
So this is the worst case that we're trying to think of.

499
00:22:48,840 --> 00:22:49,080
Right.

500
00:22:49,080 --> 00:22:52,350
So the worst case will happen if there is no cycle right.

501
00:22:52,350 --> 00:22:56,760
So that means that every vertex at some point will come into the stack.

502
00:22:56,760 --> 00:23:02,850
So we can say that this while loop over here is going to operate a total of n times, where n is the

503
00:23:02,850 --> 00:23:03,780
number of vertices.

504
00:23:03,780 --> 00:23:09,450
Now inside this we are going to decrement the neighbors by one right.

505
00:23:09,450 --> 00:23:11,130
For each of these instances.

506
00:23:11,130 --> 00:23:13,830
Now the neighbors will depend on the edges, right?

507
00:23:13,830 --> 00:23:20,580
So when we come to zero, when we pop zero, we will only do one operation because we just have one.

508
00:23:20,580 --> 00:23:22,980
When we pop one, we are going to do two operations.

509
00:23:22,980 --> 00:23:25,680
When we pop three, we are going to do three operations.

510
00:23:25,680 --> 00:23:28,140
When we pop four, we are going to do one operation, right.

511
00:23:28,140 --> 00:23:30,120
So that's the total number of operations.

512
00:23:30,120 --> 00:23:33,810
So let's just count it one, two, three, four, five, six and seven.

513
00:23:33,810 --> 00:23:35,460
So this is seven operations.

514
00:23:35,460 --> 00:23:41,220
And you can see that the number of edges over here is 7123456 and seven.

515
00:23:41,220 --> 00:23:44,370
So over here we are going to do in total right.

516
00:23:44,370 --> 00:23:46,680
The while loop is going to operate n times.

517
00:23:46,680 --> 00:23:53,730
And when if you add the total operations of this part over across all these N operations of the while

518
00:23:53,730 --> 00:23:55,440
loop, it's going to be equal to E.

519
00:23:55,440 --> 00:23:59,610
That's why this part over here is going to have N plus E operations.

520
00:23:59,610 --> 00:24:02,190
So that's why we will just add these two together.

521
00:24:02,190 --> 00:24:07,950
And we get that the time complexity of this solution is of the order of p plus n plus e.

522
00:24:07,950 --> 00:24:09,240
Again we have n and n.

523
00:24:09,240 --> 00:24:11,490
So we can say two n but two is a constant.

524
00:24:11,490 --> 00:24:13,320
So we just remove it and we get that.

525
00:24:13,320 --> 00:24:19,080
The time complexity of this solution is of the order of p plus n plus e, p is the number of elements

526
00:24:19,080 --> 00:24:22,920
in the prerequisite array, n is the number of vertices, and e is the number of edges.

527
00:24:22,920 --> 00:24:24,900
Now what about the space complexity?

528
00:24:25,440 --> 00:24:31,500
The space complexity of this solution is going to be of the order of n plus e, where n is the vertices

529
00:24:31,500 --> 00:24:32,430
and e is the edges.

530
00:24:32,430 --> 00:24:32,790
Right.

531
00:24:32,790 --> 00:24:35,130
Because we are going to form this adjacency list.

532
00:24:35,130 --> 00:24:35,370
Right.

533
00:24:35,370 --> 00:24:41,340
So this adjacency list is going to have it is going to take space of the order of n plus E because it's

534
00:24:41,340 --> 00:24:43,950
going to have n arrays right inside the array.

535
00:24:43,980 --> 00:24:45,090
They are going to be n arrays.

536
00:24:45,090 --> 00:24:48,750
And then the elements in those arrays will depend on the edges.

537
00:24:48,750 --> 00:24:50,040
So that's what we are having over here.

538
00:24:50,040 --> 00:24:50,250
Right.

539
00:24:50,250 --> 00:24:52,860
So this is going to take space of the order of n plus e.

540
00:24:52,890 --> 00:24:57,390
So that's why the space complexity of the solution is of the order of n plus e.

541
00:24:57,420 --> 00:24:59,160
What are the other things that take up space.

542
00:24:59,160 --> 00:25:05,070
So we can see that this indegree array is also taking up space which will be of the order of n that

543
00:25:05,070 --> 00:25:06,210
is less than n plus e.

544
00:25:06,210 --> 00:25:09,300
So we can neglect that we have this stack over here.

545
00:25:09,300 --> 00:25:14,700
Now the stack will only contain elements which have an indegree factor of zero.

546
00:25:14,700 --> 00:25:20,880
Now let's say the nodes were all disconnected so that every node has an indegree factor of zero.

547
00:25:20,880 --> 00:25:26,790
In that case, the that would be the worst space complexity for the stack, and in the worst case,

548
00:25:26,790 --> 00:25:29,880
the stack can take only O of n space complexity.

549
00:25:29,880 --> 00:25:33,960
So that's why among all of these, this is the greatest space which is taken up.

550
00:25:33,960 --> 00:25:39,360
And hence we can conclude that the space complexity of this solution is of the order of n plus e.

551
00:25:39,540 --> 00:25:40,080
All right.

552
00:25:40,110 --> 00:25:46,800
Now one last point to keep in mind is we have seen the time complexity is O of n plus p plus e.

553
00:25:46,830 --> 00:25:49,140
The space complexity is O of n plus e.

554
00:25:49,170 --> 00:25:55,560
Now, in the worst case E the number of edges can be of the order of n square.

555
00:25:55,560 --> 00:25:55,920
All right.

556
00:25:55,920 --> 00:25:57,330
So when will that happen?

557
00:25:57,330 --> 00:25:59,880
Let's say our graph looks something like this.

558
00:26:00,480 --> 00:26:01,920
Again it's a directed graph.

559
00:26:01,920 --> 00:26:05,430
So from this node there is a connection to every other node.

560
00:26:05,430 --> 00:26:10,320
And then from this node there is a connection to every other node except this node and so on and so

561
00:26:10,320 --> 00:26:10,650
forth.

562
00:26:10,650 --> 00:26:15,270
So we can say that there are n minus one connections over here, n minus two connections over here,

563
00:26:15,270 --> 00:26:17,550
n minus three connections over here etc..

564
00:26:17,550 --> 00:26:17,820
Right.

565
00:26:17,820 --> 00:26:23,970
So in this case the total number of connections or edges would be n minus one plus n minus two, etc.

566
00:26:23,970 --> 00:26:27,420
up to one which is equal to n minus one into n by two.

567
00:26:27,420 --> 00:26:30,900
And this over here will have an n square term when we simplify it.

568
00:26:30,900 --> 00:26:33,690
Therefore, this is going to be of the order of n square.

569
00:26:33,690 --> 00:26:39,510
So we can see that the number of edges in the worst case possibility is going to be of the order of

570
00:26:39,510 --> 00:26:40,050
n square.

571
00:26:40,050 --> 00:26:45,690
So if we substitute that over here, we can see that the time complexity is going to be of the order

572
00:26:45,690 --> 00:26:47,760
of p plus n square.

573
00:26:48,630 --> 00:26:53,580
Right because we have an n, but among n and N square n square is going to be greater.

574
00:26:53,580 --> 00:26:54,810
So we can neglect this.

575
00:26:54,810 --> 00:27:00,450
And the space complexity is going to be of the order of just n square, because again we have n and

576
00:27:00,450 --> 00:27:03,210
n square, and n square is going to be greater than n.

577
00:27:03,210 --> 00:27:08,760
So we can say that in the worst case, the time complexity is going to be of the order of p plus n square,

578
00:27:08,760 --> 00:27:12,540
and the space complexity is going to be of the order of n square.