1
00:00:00,750 --> 00:00:02,969
Hi, everyone, welcome to this new video.

2
00:00:03,090 --> 00:00:07,830
So in this video, we are going to write the code for this problem cause schedule.

3
00:00:09,240 --> 00:00:14,180
And as discussed in our previous video, I'm going to write the code for topological chart.

4
00:00:14,730 --> 00:00:17,280
So what is topological thought and how it works?

5
00:00:17,490 --> 00:00:22,260
So all of these things we have covered in our previous videos in topological short video.

6
00:00:22,590 --> 00:00:22,980
Right.

7
00:00:23,010 --> 00:00:27,420
So before writing topological thought, what we should have we should have one graph.

8
00:00:28,710 --> 00:00:29,100
Right.

9
00:00:29,280 --> 00:00:33,170
So given this input, we need to create graph out of it.

10
00:00:33,390 --> 00:00:37,700
Now, graph can be implemented via two ways at the center matrix and at the center list.

11
00:00:37,920 --> 00:00:38,340
Right.

12
00:00:38,520 --> 00:00:46,730
So we can implement our DNA matrix or we can use our list so we can use any one of them.

13
00:00:46,740 --> 00:00:54,570
Let's say I am using list, so let's create a graph and I'm going to use a list.

14
00:00:54,810 --> 00:01:00,330
So suppose this is our graph, let's say, for one, two and three.

15
00:01:01,590 --> 00:01:02,610
This is my graph.

16
00:01:03,630 --> 00:01:06,100
So how it will look like in addition to the list.

17
00:01:06,420 --> 00:01:08,460
So these are nodes.

18
00:01:08,460 --> 00:01:09,900
One, two, three.

19
00:01:10,840 --> 00:01:13,650
Let's remove three, one, two.

20
00:01:13,650 --> 00:01:16,240
And so one, two and four.

21
00:01:16,680 --> 00:01:17,610
So what will happen?

22
00:01:18,270 --> 00:01:22,470
So after one, one is pointing towards three.

23
00:01:22,500 --> 00:01:26,820
So in the list of one, I will have three node three four two.

24
00:01:26,820 --> 00:01:30,260
Two is also two can also reach two vertex three.

25
00:01:30,270 --> 00:01:33,300
So in their list I will have three, four, four.

26
00:01:33,330 --> 00:01:41,250
I can reach to either one or two, so I will have one and two and three can not reach anywhere.

27
00:01:41,250 --> 00:01:43,410
So I didn't see list of three is empty.

28
00:01:43,590 --> 00:01:47,370
So basically three will not be present in our DNC list.

29
00:01:47,520 --> 00:01:47,940
Right.

30
00:01:49,800 --> 00:01:53,190
So three will not be the only one to unfold.

31
00:01:54,450 --> 00:02:03,750
Now, if it is like three is also pointing towards, let's say five and six, that in that case I will

32
00:02:03,750 --> 00:02:07,410
also have three and is a list of three.

33
00:02:07,410 --> 00:02:08,479
I will have five and six.

34
00:02:08,669 --> 00:02:10,680
So this is the first step that we need to do.

35
00:02:10,680 --> 00:02:15,180
We need to make a list out of this closet at night.

36
00:02:15,410 --> 00:02:16,890
So let's start doing that.

37
00:02:19,370 --> 00:02:22,880
So we need a list, so this is an order to map.

38
00:02:27,510 --> 00:02:32,040
We have one map, right, map of integer and.

39
00:02:33,040 --> 00:02:33,790
One last.

40
00:02:38,010 --> 00:02:39,090
Let's say Grauwe.

41
00:02:44,260 --> 00:02:52,080
So what I'm doing here, see, what is this, this is nothing but a map, right?

42
00:02:52,270 --> 00:02:55,390
This is a map and in map waterski.

43
00:02:55,840 --> 00:02:57,760
So key is basically integer.

44
00:02:58,870 --> 00:03:00,040
And what is value?

45
00:03:00,040 --> 00:03:03,010
Value is basically a list, that list of integers.

46
00:03:03,220 --> 00:03:06,700
So key is integer and value is a list of integers.

47
00:03:07,120 --> 00:03:07,540
Right.

48
00:03:09,650 --> 00:03:17,480
OK, so let's create our graph for them to do for creating the graph we need to operate over this particular

49
00:03:17,480 --> 00:03:17,810
today.

50
00:03:19,370 --> 00:03:20,440
So I called zero.

51
00:03:20,840 --> 00:03:22,340
So the name is very big.

52
00:03:22,460 --> 00:03:24,830
Let's show the Tuppy.

53
00:03:26,720 --> 00:03:31,520
So I called zero elastin prerequisite added size.

54
00:03:34,560 --> 00:03:47,030
And I placeless, so what is a AIA's basically first element that is zeroth element and what is being.

55
00:03:49,100 --> 00:03:54,520
So B.A. is basically your second element, that is the next one, right?

56
00:03:54,740 --> 00:04:02,300
What is A and B. So it is a given indication that this big, etc. today is MBA.

57
00:04:02,300 --> 00:04:07,440
So AA depends on being late, for example, when GOMAA four.

58
00:04:07,750 --> 00:04:10,340
So when is a coffee for his buffet.

59
00:04:10,340 --> 00:04:11,860
So one depends on four.

60
00:04:11,870 --> 00:04:14,350
That is four in the list of four.

61
00:04:14,360 --> 00:04:16,700
I will have one right like this.

62
00:04:17,490 --> 00:04:19,649
So one is depending upon four.

63
00:04:20,329 --> 00:04:28,190
So what we need to do graph of B I so what this graph of B one list.

64
00:04:28,190 --> 00:04:28,580
Right.

65
00:04:28,760 --> 00:04:36,550
So in that list I need to insert of I thought I need to insert AA.

66
00:04:37,190 --> 00:04:38,740
So now my graph is ready.

67
00:04:39,740 --> 00:04:40,130
Right.

68
00:04:40,400 --> 00:04:41,870
My graph is ready now.

69
00:04:42,700 --> 00:04:46,400
So after creating this graph, what is the next step in topological chart.

70
00:04:46,730 --> 00:04:53,760
So next step is basically you need to populate in degree at a rate we need to create integrity.

71
00:04:53,780 --> 00:04:55,260
So how many courses are there?

72
00:04:55,700 --> 00:04:57,600
There are two, three, five courses.

73
00:04:58,280 --> 00:05:03,790
So if the number is the value of no, of course it is five, then I will create an array of size five.

74
00:05:03,800 --> 00:05:12,290
And initially the degree for all the elements at zero eight seven degrees zero, then we will iterate

75
00:05:12,290 --> 00:05:13,100
over this graph.

76
00:05:13,820 --> 00:05:20,810
So what is the degree for for so negative four for will be zero in degree of one when.

77
00:05:21,890 --> 00:05:23,600
What is the degree of two again.

78
00:05:23,600 --> 00:05:23,900
One.

79
00:05:24,140 --> 00:05:24,740
What is it.

80
00:05:24,740 --> 00:05:25,570
Degree of three.

81
00:05:25,610 --> 00:05:26,480
It is two.

82
00:05:26,870 --> 00:05:27,270
Right.

83
00:05:27,290 --> 00:05:29,470
So we need to populate this integrity.

84
00:05:30,500 --> 00:05:39,530
So for populating this in degree array what we can do, let's first create this integrity and integrity.

85
00:05:40,970 --> 00:05:44,810
What will be it says it size will be the number of courses you have.

86
00:05:46,320 --> 00:05:51,450
And what we need to do initially indicated for all the elements is zero.

87
00:05:51,810 --> 00:05:54,960
So instead of using integer, let's use Vector here.

88
00:05:58,200 --> 00:06:05,070
So Victor and degree, so how many courses are there, what would be the size of the victor number of

89
00:06:05,070 --> 00:06:10,870
courses and we need to initialize with zero, so initialized with zero, right.

90
00:06:11,030 --> 00:06:12,720
So what is the effect of this line?

91
00:06:13,380 --> 00:06:19,860
So where this line will do this line will create this vector and it will initialize all the values to

92
00:06:19,860 --> 00:06:20,320
zero.

93
00:06:20,670 --> 00:06:26,590
So what is the size of the vector number of courses and what to value to initialize initialized to zero?

94
00:06:26,850 --> 00:06:31,520
So all the values will be initialized to zero and that is what we want.

95
00:06:33,480 --> 00:06:36,120
Now we need to fill this in degree area also.

96
00:06:36,150 --> 00:06:36,560
Right.

97
00:06:37,080 --> 00:06:38,710
And how we can do that.

98
00:06:39,030 --> 00:06:45,570
So when you are creating your graph in this loop, only you can initialize your integrity.

99
00:06:48,760 --> 00:06:53,170
So degree of AAII.

100
00:06:54,380 --> 00:06:58,610
Plus plus, that is all that you need to do, right?

101
00:07:00,410 --> 00:07:01,790
What I'm doing here is.

102
00:07:04,290 --> 00:07:13,350
So if this is the condition I have been coming for and I have to go my food and let's I have one comadre,

103
00:07:14,370 --> 00:07:19,410
so what the graph look like, one has a dependency on food.

104
00:07:21,240 --> 00:07:25,020
Who also has a dependency on food and wine also has a dependency of three.

105
00:07:25,880 --> 00:07:28,080
So this is AA.

106
00:07:28,140 --> 00:07:34,740
Remember, this is a so whenever we encounter one, whenever we encounter one, we will increment its

107
00:07:34,740 --> 00:07:35,240
integrity.

108
00:07:35,250 --> 00:07:35,550
Right.

109
00:07:35,750 --> 00:07:41,130
So I am encountering when two times, first time and this second time, what is the degree value and

110
00:07:41,130 --> 00:07:42,090
degree value is to.

111
00:07:42,420 --> 00:07:44,160
So that's why it is correct.

112
00:07:44,300 --> 00:07:44,670
Right.

113
00:07:44,910 --> 00:07:51,420
I am encountering to only one time so this will be only one time plus plus and is the degree of to only

114
00:07:51,420 --> 00:07:51,680
one.

115
00:07:52,200 --> 00:07:54,600
So that's how our integrity will be populated.

116
00:07:57,500 --> 00:08:03,560
So we have our integrity, no, and not a logical standard of logical thought, but we need to do we

117
00:08:03,560 --> 00:08:07,490
need to create Accu right and what else?

118
00:08:07,940 --> 00:08:14,070
We need to insert all the elements, all the nodes whose integrity is zero zero means independent.

119
00:08:14,090 --> 00:08:21,040
So I call zero elastin integrity darte, says I placeless.

120
00:08:22,010 --> 00:08:31,060
So if any degree of aliment I is zero, that means discourse is independent.

121
00:08:31,610 --> 00:08:36,260
Since discourse is independent, it must be present in the queue.

122
00:08:36,440 --> 00:08:39,530
So could not push a simple.

123
00:08:41,690 --> 00:08:48,530
Now, a standard topological sort part to embody, so while Geldart says.

124
00:08:50,370 --> 00:08:51,600
Is greater than zero.

125
00:08:54,200 --> 00:09:02,000
So while MICU is not empty, what I will do, I will pop one element, let's say Naude, that will be

126
00:09:02,000 --> 00:09:03,640
good old friend.

127
00:09:05,180 --> 00:09:13,220
And so after popping the element, but we need to do since we have visited one element, right.

128
00:09:14,000 --> 00:09:16,340
Litzman Dana Count visited the number.

129
00:09:16,340 --> 00:09:20,590
Of course I have installed and finished, so finished.

130
00:09:21,440 --> 00:09:23,720
So how many courses I have finished as of now.

131
00:09:23,720 --> 00:09:26,360
Zero now.

132
00:09:28,170 --> 00:09:35,040
What I will do, the finished courses plus plus rate, I am taking one element out of the queue and

133
00:09:35,040 --> 00:09:38,970
I am enrolling that into that course and I am finishing that course.

134
00:09:38,970 --> 00:09:47,610
So I finished courses plus plus after that, what we need to do, we need to go to all each child so

135
00:09:47,610 --> 00:09:51,210
each child will be we will get a list of child.

136
00:09:51,690 --> 00:09:52,130
Right.

137
00:09:52,890 --> 00:09:54,090
So all its children.

138
00:09:55,410 --> 00:10:01,650
So how many children's graph of Naude GDP, each graph of Noad.

139
00:10:02,130 --> 00:10:05,310
We will get all the children right.

140
00:10:05,550 --> 00:10:12,450
So for example, let's say this is one, this is two, three and four.

141
00:10:13,140 --> 00:10:16,780
So coast to coast, three and four, they have a dependency on this one.

142
00:10:17,010 --> 00:10:19,500
So in Cuba, you have goals one.

143
00:10:20,170 --> 00:10:23,830
Right, because for course, one in degree was zero.

144
00:10:24,840 --> 00:10:35,430
Now, after that, what you are doing pop the element from the Q and in the map I have this list two,

145
00:10:35,430 --> 00:10:36,150
three and four.

146
00:10:36,630 --> 00:10:41,730
Wait, so pop the element finished courses plus plus I finished the course one.

147
00:10:42,390 --> 00:10:45,090
Now from the graph I will give Norvan.

148
00:10:45,450 --> 00:10:49,350
So if I give an order one I will get all children two, three and four.

149
00:10:49,560 --> 00:10:51,600
So two, three and four added children.

150
00:10:52,830 --> 00:10:53,200
Right.

151
00:10:53,220 --> 00:10:56,100
So what we need to do, we need to reduce their degree by one.

152
00:10:56,430 --> 00:11:01,200
So in degree of two will reduce violence or it will become zero and negative three but will reduce by

153
00:11:01,200 --> 00:11:01,410
one.

154
00:11:01,410 --> 00:11:06,960
So it will become zero in degree of four will be reduced by one because course one has been finished.

155
00:11:07,300 --> 00:11:09,180
So degree will become a zero.

156
00:11:09,300 --> 00:11:09,690
Right.

157
00:11:11,880 --> 00:11:14,450
So in degree becomes zero, zero and zero.

158
00:11:15,810 --> 00:11:20,520
So what we need to do, we need to trade over the children.

159
00:11:21,030 --> 00:11:23,310
So let's I treat all the children.

160
00:11:24,000 --> 00:11:25,860
So I will start from zero.

161
00:11:25,860 --> 00:11:28,980
I lost ten children.

162
00:11:28,980 --> 00:11:33,350
Dart sighs and I placeless.

163
00:11:33,900 --> 00:11:39,540
What we need to do, we need to reduce the integrity of the children.

164
00:11:39,840 --> 00:11:43,590
So in degree of yet child minus.

165
00:11:43,590 --> 00:11:45,090
Minus right.

166
00:11:45,510 --> 00:11:52,890
And if if the degree becomes zero C here the degree becomes zero.

167
00:11:53,550 --> 00:11:55,170
Zero means independent.

168
00:11:55,170 --> 00:12:00,210
Independent means they should be part of Q so I will insert two, three and four inside.

169
00:12:00,210 --> 00:12:01,350
Q Right.

170
00:12:02,010 --> 00:12:03,600
The standard topological start.

171
00:12:06,930 --> 00:12:11,110
So if what we need to do, yes, we need to check.

172
00:12:11,460 --> 00:12:15,210
So if the integrity of a yet child.

173
00:12:17,770 --> 00:12:27,040
Becomes zero, that means this cause is independent, since this cause is now independent, this cause

174
00:12:27,370 --> 00:12:32,560
should be present in our Q So push the eighth child in dequeue.

175
00:12:33,250 --> 00:12:34,850
Right, and that's it.

176
00:12:35,270 --> 00:12:38,410
Finally, how many courses you have finished?

177
00:12:38,440 --> 00:12:41,760
You have finished these many number of courses, right?

178
00:12:42,130 --> 00:12:47,710
So I have finished these many number of courses and how many courses I need to finish.

179
00:12:48,190 --> 00:12:50,280
So I need to finish these courses.

180
00:12:50,290 --> 00:12:51,400
No courses.

181
00:12:53,680 --> 00:12:58,460
So if these two values are equal, I will return true, otherwise I will return false.

182
00:12:59,440 --> 00:13:00,070
So that's it.

183
00:13:01,240 --> 00:13:05,390
So let me go through the entire record once, then we will run this code.

184
00:13:06,520 --> 00:13:11,080
So first of all, we are creating the graph because for topological chart, we need graph.

185
00:13:11,290 --> 00:13:15,910
Similarly, for topological chart, we need to create this in the gray area, which is initialized to

186
00:13:15,910 --> 00:13:16,270
zero.

187
00:13:17,590 --> 00:13:20,940
Right then I am migrating over this picture today.

188
00:13:20,980 --> 00:13:28,150
I am constructing the graph, I am using the list and then I am setting the integrity value rate for

189
00:13:28,150 --> 00:13:28,990
all the elements.

190
00:13:29,320 --> 00:13:31,060
Then I am maltreating or the integrity.

191
00:13:31,270 --> 00:13:34,970
If any course is independent, then it must be present in queue.

192
00:13:35,770 --> 00:13:37,260
Then finally, what we need to do.

193
00:13:37,300 --> 00:13:43,030
I am calculating how many courses I have finished rate, so we need to finish these many number of course

194
00:13:43,030 --> 00:13:44,710
is the name of the function is can finish.

195
00:13:45,100 --> 00:13:47,610
So currently I have not finished any of the courses.

196
00:13:47,950 --> 00:13:53,230
So while class size is greater than zero, while there are elements in the queue, the different elements

197
00:13:53,270 --> 00:13:54,490
of the element of the queue.

198
00:13:55,060 --> 00:14:01,240
And since I have completed this course, so number of finished courses plus plus then go to all the

199
00:14:01,240 --> 00:14:04,480
child and reduce their in degree by one.

200
00:14:04,810 --> 00:14:09,340
And if their degree becomes zero, that means that courses have now become independent.

201
00:14:09,610 --> 00:14:11,020
So they should be part of.

202
00:14:11,020 --> 00:14:11,770
Q Right.

203
00:14:11,830 --> 00:14:12,910
So push in dequeue.

204
00:14:13,090 --> 00:14:19,190
And finally, if the number of courses I have finished is equal to the number of courses I want to finish.

205
00:14:19,210 --> 00:14:22,000
If these two values are equal, I will return true.

206
00:14:22,000 --> 00:14:26,050
Otherwise I will return false so that that will be the complete code.

207
00:14:26,620 --> 00:14:31,530
So let's try to run our code and see whether our code has some bug or it is correct.

208
00:14:35,240 --> 00:14:39,740
So we have some back here, OK, compilation error.

209
00:14:45,540 --> 00:14:47,220
Yeah, let's try to sum it up, Gore.

210
00:14:50,740 --> 00:14:59,410
Yeah, so basically our goal is working late, so this is the entire code and as I discussed also,

211
00:14:59,740 --> 00:15:02,530
so I have solved this problem using topological thought.

212
00:15:02,530 --> 00:15:05,950
The other way of solving this problem is basically cycle detection algorithm.

213
00:15:05,950 --> 00:15:06,280
Right.

214
00:15:07,090 --> 00:15:09,430
So for cycle detection algorithm, what will do?

215
00:15:09,790 --> 00:15:12,370
You have created the graph rate.

216
00:15:12,460 --> 00:15:15,310
So in cyclodextrin algorithm, you also need to create one graph.

217
00:15:15,460 --> 00:15:20,020
And after creating the graph, you can implement cycle detection algorithm, which is implemented using

218
00:15:20,020 --> 00:15:20,620
DFS.

219
00:15:21,820 --> 00:15:23,320
So you can use this algorithm.

220
00:15:23,320 --> 00:15:27,270
Also our you can use topological sword, right?

221
00:15:27,460 --> 00:15:29,100
So it's your choice.

222
00:15:29,110 --> 00:15:30,260
You can do any of them.

223
00:15:30,280 --> 00:15:35,410
So this is all about this weird device that is pretty much that I want to discuss in this video.

224
00:15:36,400 --> 00:15:39,970
So if you have any doubt to ask me, I will see you in the next one.

225
00:15:40,300 --> 00:15:40,970
Thank you.

226
00:15:40,990 --> 00:15:41,470
Bye bye.

