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.