1 00:00:01,359 --> 00:00:02,110 Hi, everyone. 2 00:00:02,140 --> 00:00:08,590 So in this video, we are going to discuss about disjoint sets, why we are discussing this, because 3 00:00:08,590 --> 00:00:12,460 we have seen in the algorithm we need a cyclodextrin algorithm. 4 00:00:12,640 --> 00:00:15,360 So with the help of disjoined that we can detect cycle. 5 00:00:16,270 --> 00:00:18,460 So how disjointed works. 6 00:00:18,700 --> 00:00:25,780 So there will be three Operation IT Union and find and these are the corresponding definitions. 7 00:00:27,010 --> 00:00:32,800 So you can reach the definition, but you will be able to understand the definition when we will take 8 00:00:32,800 --> 00:00:33,460 one example. 9 00:00:33,790 --> 00:00:34,990 So this is one graph. 10 00:00:37,910 --> 00:00:43,880 A graph will be given to us, so first of all, what we need to do, we will call the function, Mique 11 00:00:43,880 --> 00:00:44,360 said. 12 00:00:45,020 --> 00:00:46,280 We will call function. 13 00:00:48,900 --> 00:00:55,650 Makes it on all the witnesses call me, except for all the word for word, text one word, text two 14 00:00:55,650 --> 00:00:57,590 or three, four, five, six and seven. 15 00:00:58,020 --> 00:01:04,650 So after calling the Mxit function what it will do, it will create a set with one element. 16 00:01:05,069 --> 00:01:06,920 So I'm going to create sets. 17 00:01:07,230 --> 00:01:15,360 So that means this is one third one element, one set of one element, one set of one element, one 18 00:01:15,360 --> 00:01:23,580 set of one element, one set of one element, one set of one element and one set of one element. 19 00:01:23,790 --> 00:01:29,080 So what it does, it create it creates it with one element. 20 00:01:29,520 --> 00:01:35,190 So since I have called make certain all the vertices it has created sets with one element. 21 00:01:35,190 --> 00:01:35,590 Right. 22 00:01:35,640 --> 00:01:38,960 This is the first thing that we need to do why we are doing this. 23 00:01:38,970 --> 00:01:41,810 You will be able to understand when it will go through the whole video. 24 00:01:41,940 --> 00:01:48,840 So after calling the Miksad what we need to do, we will call the function unión. 25 00:01:50,010 --> 00:01:51,540 We will call the function union. 26 00:01:51,540 --> 00:01:56,950 What union does is it takes to set and it merge them into one. 27 00:01:57,870 --> 00:01:59,970 For example, if I am calling unión. 28 00:02:02,330 --> 00:02:03,470 When Commodore. 29 00:02:05,310 --> 00:02:11,560 So this one element belongs to the set, the element to belongs to this. 30 00:02:12,090 --> 00:02:15,960 So what it does is basically it combined the set. 31 00:02:16,350 --> 00:02:19,770 So it will combine and this is my new sect. 32 00:02:20,550 --> 00:02:22,360 So remove one remove, too. 33 00:02:22,650 --> 00:02:24,840 And this is our new set, one and two. 34 00:02:25,500 --> 00:02:27,150 Right work find function. 35 00:02:27,150 --> 00:02:30,540 Does it find the representative element for that sect? 36 00:02:30,960 --> 00:02:34,940 So this site is containing two elements, one and two. 37 00:02:35,730 --> 00:02:43,590 So if I can find one and if I go, I'll find two, then the answer should be same. 38 00:02:44,610 --> 00:02:45,750 Answer should be same. 39 00:02:45,780 --> 00:02:52,820 So what I am trying to say here is there must be one representative element that represents the whole 40 00:02:52,830 --> 00:02:53,080 set. 41 00:02:53,430 --> 00:02:58,470 So in that case, see here we have only one element so that one element represent the whole set. 42 00:02:58,770 --> 00:03:00,350 Here we have only one element. 43 00:03:00,350 --> 00:03:02,400 So this element to represent the whole state. 44 00:03:02,790 --> 00:03:06,500 But this is our new set and this set contains two element. 45 00:03:06,750 --> 00:03:10,020 So one element will be the representative element for that. 46 00:03:10,110 --> 00:03:17,160 It let's say one element, one is Diddy presented to find one will give you the representative element. 47 00:03:17,160 --> 00:03:21,840 Representative element is one find to what it returns. 48 00:03:21,840 --> 00:03:24,410 It returns the representative element for that set. 49 00:03:24,720 --> 00:03:30,080 So to belongs to the set and the representative element for this at this one. 50 00:03:30,150 --> 00:03:31,320 So the answer will be one. 51 00:03:32,740 --> 00:03:33,240 Right. 52 00:03:34,770 --> 00:03:36,210 Let's take one more example. 53 00:03:36,420 --> 00:03:38,970 I want to find the union for two and three. 54 00:03:40,380 --> 00:03:42,620 What will be the union for two and three? 55 00:03:43,860 --> 00:03:49,950 So two belongs to this third and three belongs to the third. 56 00:03:50,670 --> 00:03:56,520 So if we will take the union, then it will be one khama two comadre right. 57 00:03:56,670 --> 00:04:04,020 I will be adding myself to belongs to the third and three belongs to the set and we want to take union. 58 00:04:04,020 --> 00:04:08,070 And where does the union take to third and merge them into one. 59 00:04:09,000 --> 00:04:10,160 So I have merged them. 60 00:04:10,740 --> 00:04:13,880 Now again this site is containing three elements. 61 00:04:14,640 --> 00:04:18,990 So one element we need to pick one element as the representative element. 62 00:04:19,320 --> 00:04:23,030 Let's say I am picking one as the representative element. 63 00:04:23,460 --> 00:04:27,750 So find out when one belongs to the set. 64 00:04:28,320 --> 00:04:29,910 And what is the representative element? 65 00:04:29,910 --> 00:04:30,480 One only. 66 00:04:31,680 --> 00:04:32,640 Find of two. 67 00:04:34,520 --> 00:04:40,070 Who belongs to this set and for this said, representative development is one, so answer will be one, 68 00:04:41,090 --> 00:04:41,960 find three. 69 00:04:44,370 --> 00:04:50,620 Three belongs to the third and the representative element for this site is one Sudan. 70 00:04:50,760 --> 00:04:51,270 Will be one. 71 00:04:52,230 --> 00:04:54,180 So you understand what is the meaning of find? 72 00:04:54,720 --> 00:04:57,960 Find will return you the representative element for that said. 73 00:05:00,130 --> 00:05:09,550 Let's take a few more example, I want to find the union of four and five, so four belongs to the third 74 00:05:10,030 --> 00:05:11,780 and five belongs to the third. 75 00:05:12,220 --> 00:05:13,350 So we will merge them. 76 00:05:13,930 --> 00:05:16,630 So this is our new set, four and five. 77 00:05:17,590 --> 00:05:17,980 Right. 78 00:05:18,280 --> 00:05:23,230 And again, we're trying to do since this spat, this set is continuing to element. 79 00:05:23,230 --> 00:05:25,990 So we need to pick one element as the representatively. 80 00:05:26,620 --> 00:05:29,410 Let's say forward is the representative element. 81 00:05:30,400 --> 00:05:37,550 So what is final four to four belongs to the set and the representative element for this episode. 82 00:05:37,570 --> 00:05:40,690 So let's wait for what will be final five. 83 00:05:41,080 --> 00:05:43,690 Find five belongs to the third. 84 00:05:44,500 --> 00:05:51,490 And the representative element for the status for the final five will be for next week when, for example, 85 00:05:51,490 --> 00:05:57,040 I want to find the union of let's say five, let's say six and seven. 86 00:05:59,190 --> 00:06:07,050 So six belongs to the third, seven belongs to the third, so union will merge them six and seven. 87 00:06:07,230 --> 00:06:10,040 And again, it is containing more than one element. 88 00:06:10,050 --> 00:06:12,780 So we need to pick one element as the representative element. 89 00:06:13,150 --> 00:06:14,580 Let's say I am picking success. 90 00:06:14,580 --> 00:06:15,790 They represented the element. 91 00:06:16,050 --> 00:06:17,550 So what will be find of six? 92 00:06:17,580 --> 00:06:18,410 It will be six. 93 00:06:18,750 --> 00:06:20,600 What is kind of seven? 94 00:06:21,060 --> 00:06:22,640 Eight will be seven. 95 00:06:22,660 --> 00:06:26,430 So it will be six because seven belongs to the state now. 96 00:06:26,580 --> 00:06:29,420 And the representative element for this sect is six. 97 00:06:29,580 --> 00:06:30,630 So that's why six. 98 00:06:31,680 --> 00:06:32,460 Simple, right. 99 00:06:32,880 --> 00:06:34,470 Let's take one more example. 100 00:06:35,400 --> 00:06:39,870 I want to find the union of, let's say five and six. 101 00:06:41,410 --> 00:06:43,150 So where does five belongs? 102 00:06:43,980 --> 00:06:46,550 So five belongs to the state. 103 00:06:46,710 --> 00:06:47,940 This one, right. 104 00:06:48,660 --> 00:06:49,890 Five belongs here. 105 00:06:49,890 --> 00:06:51,000 And where six. 106 00:06:51,420 --> 00:06:52,610 Six belongs here. 107 00:06:52,620 --> 00:06:54,810 So we need to merge these two states. 108 00:06:55,290 --> 00:06:56,340 So let's merge them. 109 00:06:56,490 --> 00:06:59,300 It will become four, five, six and seven. 110 00:06:59,700 --> 00:07:02,280 And again, this are is containing more than one element. 111 00:07:02,290 --> 00:07:07,890 So we need to pick one element as the representative elements so either you can pick four or you can 112 00:07:07,890 --> 00:07:08,660 pick six. 113 00:07:09,000 --> 00:07:10,620 Let's say I am picking for. 114 00:07:11,220 --> 00:07:14,040 So what is final four here? 115 00:07:14,070 --> 00:07:15,960 Or find a five of six. 116 00:07:15,960 --> 00:07:16,680 Five of seven. 117 00:07:17,310 --> 00:07:18,780 All the answer will be four. 118 00:07:20,520 --> 00:07:21,030 Right. 119 00:07:23,510 --> 00:07:30,290 Find affordable before find five belongs to the set and the representative, so find a fight will be 120 00:07:30,290 --> 00:07:34,980 fought and similarly find 06 and 07 will also be fought. 121 00:07:35,660 --> 00:07:38,120 So that's why I have written Actovegin one. 122 00:07:38,120 --> 00:07:38,590 Go ahead. 123 00:07:39,830 --> 00:07:41,440 Now, let's take one more example. 124 00:07:41,990 --> 00:07:45,830 I want to find a union of three and seven. 125 00:07:46,720 --> 00:07:47,820 So there is three. 126 00:07:48,980 --> 00:07:51,260 Three is present here, right? 127 00:07:51,960 --> 00:07:53,150 Three is present here. 128 00:07:53,660 --> 00:07:54,850 Where is seven? 129 00:07:55,190 --> 00:07:57,000 So seven is present here. 130 00:07:57,320 --> 00:08:03,540 So what we need to do, what the unions say is union say is to set and merge them into one. 131 00:08:04,100 --> 00:08:05,180 So we need to merge them. 132 00:08:06,230 --> 00:08:10,610 So we need to merge one, two, three, four, five, six and seven. 133 00:08:11,060 --> 00:08:16,190 So this will be one, two, three, four, five, six and seven. 134 00:08:16,940 --> 00:08:22,010 So Representative Element four, this is for representative development for this latest one. 135 00:08:22,430 --> 00:08:25,000 So again, the site is containing more than one element. 136 00:08:25,010 --> 00:08:27,650 So you need to pick one element as the representative element. 137 00:08:27,980 --> 00:08:31,400 Either it will be one or it will be for it's our choice. 138 00:08:31,640 --> 00:08:37,490 We can select one or we can select for let's say we are selecting for as the representative element 139 00:08:37,490 --> 00:08:38,570 for this set. 140 00:08:39,200 --> 00:08:39,570 Right. 141 00:08:39,950 --> 00:08:41,700 So what will be fired off? 142 00:08:41,720 --> 00:08:45,460 One friend of one will be one belongs to the state. 143 00:08:45,470 --> 00:08:51,650 No representative element is for some kind of one will be for similarly defined of two forward firing 144 00:08:51,650 --> 00:08:55,250 of three four final five before five of six will be four. 145 00:08:55,490 --> 00:08:59,390 Five of seven will be for the firing of all the elements. 146 00:09:02,760 --> 00:09:04,740 Is going to be food. 147 00:09:05,580 --> 00:09:07,530 So what is fine, fine. 148 00:09:07,580 --> 00:09:10,790 Basically, we'll give you the representative element for that said. 149 00:09:11,220 --> 00:09:14,420 So all the elements is present in the set. 150 00:09:15,060 --> 00:09:20,970 So representative element is hard to find for all the elements will give you a representative element, 151 00:09:20,970 --> 00:09:21,760 which is food. 152 00:09:22,740 --> 00:09:30,330 So I hope you have understood what is the meaning of Miksad, what is the meaning of a union and what 153 00:09:30,330 --> 00:09:31,500 is the meaning of find. 154 00:09:32,640 --> 00:09:33,090 Right. 155 00:09:33,210 --> 00:09:37,110 These three functions are very important to understand for cyclodextrin. 156 00:09:37,140 --> 00:09:39,720 So now we are able to understand these functions. 157 00:09:39,910 --> 00:09:40,380 Right. 158 00:09:40,590 --> 00:09:48,510 And one more thing to note here is whenever I am saying said said means component connected component 159 00:09:49,050 --> 00:09:52,480 in terms of Grauwe certain means connected component. 160 00:09:53,520 --> 00:09:56,330 So I am saying here that this is one set. 161 00:09:57,510 --> 00:09:59,910 So this means this is one connected component. 162 00:10:00,240 --> 00:10:01,240 This is one set. 163 00:10:01,260 --> 00:10:02,910 This is another connected component. 164 00:10:03,210 --> 00:10:04,400 This is another set. 165 00:10:04,410 --> 00:10:06,030 This is another connected component. 166 00:10:06,330 --> 00:10:09,360 So set and component they both seem. 167 00:10:09,520 --> 00:10:17,220 So if I see two elements in the same set, two elements in the same set, for example, one, two, 168 00:10:17,220 --> 00:10:17,470 three. 169 00:10:17,970 --> 00:10:19,230 So let's talk about this. 170 00:10:19,230 --> 00:10:19,830 One, two, three. 171 00:10:20,160 --> 00:10:21,690 So one, two, three. 172 00:10:22,110 --> 00:10:23,720 Dilli in the same set. 173 00:10:24,270 --> 00:10:27,950 So that means I can say they lie in the same connected component. 174 00:10:28,170 --> 00:10:31,860 That means there must have been few edges like one, two and three. 175 00:10:34,360 --> 00:10:43,480 This is one connected component I'm repeating myself, said means component to element line seems that 176 00:10:43,480 --> 00:10:46,210 means two elements in the same connected component. 177 00:10:47,080 --> 00:10:48,220 So this is one set. 178 00:10:49,610 --> 00:10:55,190 And the corresponding component, right, certain component, they both are the same. 179 00:10:55,220 --> 00:10:57,180 So now what is the next step? 180 00:10:57,200 --> 00:10:59,450 So we know makes it. 181 00:10:59,450 --> 00:11:01,130 We know union, we know find. 182 00:11:01,130 --> 00:11:02,810 We know how they will work. 183 00:11:02,820 --> 00:11:07,030 Let's try to understand how we will write the code laid the law. 184 00:11:07,070 --> 00:11:11,270 We have understood how it will work, how union will work, how fine will work. 185 00:11:11,570 --> 00:11:13,520 But we also need to write the code for them. 186 00:11:13,520 --> 00:11:13,900 Right. 187 00:11:14,510 --> 00:11:19,400 So let's write the code for them, how the code will look like. 188 00:11:22,720 --> 00:11:29,230 So here I have written the code for me, exact function, find the function and union function. 189 00:11:30,280 --> 00:11:32,410 What we need to do, we need to take one at a. 190 00:11:33,990 --> 00:11:40,020 To write the code for all these function, we need to take one at the name of the phrase apparently 191 00:11:40,020 --> 00:11:43,940 parent bearing the name of the Eddys, basically parent daddy. 192 00:11:44,700 --> 00:11:50,820 OK, so what is happening here is these are what this is vertex one, vertex two or three, vertex four, 193 00:11:50,820 --> 00:11:51,940 five, six and seven. 194 00:11:52,440 --> 00:12:01,380 So our first step was called the Miksad function for all the witnesses called mixed function for liver 195 00:12:01,380 --> 00:12:01,830 disease. 196 00:12:02,070 --> 00:12:04,110 And this makes it function. 197 00:12:04,110 --> 00:12:10,230 What it is doing Behrendorff, i.e., is a parent of one is one. 198 00:12:10,350 --> 00:12:13,710 Parent of two is to parent of three is three. 199 00:12:13,710 --> 00:12:15,000 Parent of four is four. 200 00:12:15,000 --> 00:12:16,350 Parent of five is five. 201 00:12:16,860 --> 00:12:18,930 Parent of six is six. 202 00:12:19,290 --> 00:12:21,060 Parent of seven is seven. 203 00:12:21,720 --> 00:12:24,540 So that is the first step that we need to do. 204 00:12:25,470 --> 00:12:28,470 Call the Miksad function for all the witnesses. 205 00:12:28,470 --> 00:12:31,110 And this is the definition for the Miksad function. 206 00:12:31,800 --> 00:12:37,680 So this is what X1 and parent of Vertex one is one itself. 207 00:12:38,220 --> 00:12:42,270 This is Vertex two, parent of Vertex two is to itself. 208 00:12:42,690 --> 00:12:46,680 This is Vertex three, parent of Vertex three is three itself. 209 00:12:46,770 --> 00:12:48,240 This is the meaning of this line. 210 00:12:49,020 --> 00:12:56,070 This is Vertex four, parent of Vertex for this four, parent of Vertex five is five itself, parent 211 00:12:56,070 --> 00:13:01,770 of Vertex six is six itself, parent of Vertex seven is seven itself. 212 00:13:02,010 --> 00:13:03,540 So that is the meaning of this line. 213 00:13:03,540 --> 00:13:05,880 That is how we will be able to fill this parent. 214 00:13:05,880 --> 00:13:06,840 Very simple. 215 00:13:07,620 --> 00:13:11,070 Now let's do the same thing that we were doing earlier. 216 00:13:11,850 --> 00:13:19,140 The first thing that we did was we take a union of one to remember. 217 00:13:19,980 --> 00:13:21,750 We took Union of one Komada. 218 00:13:23,010 --> 00:13:26,040 So let me show you what we will do. 219 00:13:26,700 --> 00:13:29,010 We will do all the same things again. 220 00:13:29,850 --> 00:13:35,100 You don't know when comatose, then Tucumcari then for Coma five and at last Tecoma seven. 221 00:13:35,340 --> 00:13:40,890 So I am doing all the same things again with code right now. 222 00:13:40,890 --> 00:13:43,560 We have written the code so we will see how the code will work. 223 00:13:44,070 --> 00:13:46,470 So Union of one and two. 224 00:13:46,470 --> 00:13:51,240 So for union, what I am doing this is Union X is one used. 225 00:13:51,440 --> 00:13:57,920 We are calling for end of one what this friend of one find of means the representative element. 226 00:13:57,930 --> 00:14:01,710 So one is here who is the parent of one one itself. 227 00:14:02,430 --> 00:14:03,960 So that will be fine. 228 00:14:03,960 --> 00:14:12,450 Will return you when what is kind of to, to itself find him is the representative element remember. 229 00:14:12,570 --> 00:14:20,970 And then what you are doing, parent of phase B, so basically what I am writing, this is two and the 230 00:14:20,970 --> 00:14:25,410 parent of two is now one and the parent of one is one itself. 231 00:14:25,410 --> 00:14:27,150 So this is the meaning of a union. 232 00:14:27,570 --> 00:14:35,370 In previous case I have written like this union means one, two and one was the representative element. 233 00:14:36,600 --> 00:14:39,390 I remember when was Dedee presented development. 234 00:14:39,390 --> 00:14:43,020 I have written previously like this, but how it will work and cold. 235 00:14:43,350 --> 00:14:45,630 It will work like this for the union. 236 00:14:46,710 --> 00:14:49,020 We will first find out the representative element. 237 00:14:49,290 --> 00:14:52,200 So find functional function will return you the representative element. 238 00:14:52,530 --> 00:14:54,350 This is only one element in the set. 239 00:14:54,360 --> 00:14:59,400 So representative element is one representative element is to then parent of one is two. 240 00:14:59,400 --> 00:15:01,820 So we need to update this parent, Eddie. 241 00:15:01,950 --> 00:15:03,300 So what will happen here? 242 00:15:04,290 --> 00:15:06,930 When will come here and rest? 243 00:15:06,930 --> 00:15:08,190 All the values will be same. 244 00:15:09,090 --> 00:15:14,550 So one, two, three, four, five, six and seven. 245 00:15:15,360 --> 00:15:15,780 Right. 246 00:15:16,260 --> 00:15:20,010 Parent of two is when one more thing that I want to say it is. 247 00:15:20,250 --> 00:15:23,370 It doesn't matter whether the right parent of equals B or you. 248 00:15:23,370 --> 00:15:29,930 Right parent of B calls A, you can write any one of them. 249 00:15:29,940 --> 00:15:31,170 Now let's move ahead. 250 00:15:31,470 --> 00:15:36,840 So now what we need to do is we need to find out the union for two and three. 251 00:15:37,440 --> 00:15:38,760 So this is two. 252 00:15:39,750 --> 00:15:41,070 Two corresponds to one. 253 00:15:41,970 --> 00:15:43,410 And this is the conditional. 254 00:15:43,560 --> 00:15:44,280 We have three. 255 00:15:45,030 --> 00:15:45,420 Right. 256 00:15:45,750 --> 00:15:50,970 So this history and three will point towards one now. 257 00:15:51,330 --> 00:15:53,550 And this is our said one, two, three. 258 00:15:54,840 --> 00:15:57,330 And one is the representative element. 259 00:15:58,140 --> 00:16:01,380 And similarly, we are going to update this parent, Eddie. 260 00:16:01,890 --> 00:16:03,690 So what parent would have done? 261 00:16:04,020 --> 00:16:08,830 The parent of three is one, parent of three is basically one Andrest. 262 00:16:08,880 --> 00:16:10,260 Everything will remain same. 263 00:16:11,250 --> 00:16:16,160 So one one, four, five, six and seven. 264 00:16:16,440 --> 00:16:22,410 So how I am doing this, what I am doing so I am calling the union function twenty. 265 00:16:22,680 --> 00:16:25,470 So union exists to find two. 266 00:16:26,520 --> 00:16:30,960 What find it too will return to find it will return me one. 267 00:16:31,290 --> 00:16:33,140 So Disvalue find willerton. 268 00:16:33,310 --> 00:16:37,060 Me one five out of three will return three, right? 269 00:16:37,660 --> 00:16:40,810 This is the function, this is their definition of fine function. 270 00:16:40,810 --> 00:16:43,550 So final table at entry and then what we are doing. 271 00:16:43,940 --> 00:16:52,930 So one thing here we can write parent of A equals B or we can write parent off B equals E, so let's 272 00:16:52,930 --> 00:16:56,220 do this because I have operated that in this way. 273 00:16:56,500 --> 00:16:58,630 So let's consider this and not this. 274 00:17:00,800 --> 00:17:07,800 So I'm updating parent of three to be one, parent of three is now one simple. 275 00:17:08,240 --> 00:17:10,150 Let's take one more example. 276 00:17:10,400 --> 00:17:14,359 The next one was basically we need to find out the union of four and five. 277 00:17:16,099 --> 00:17:19,319 So Ford is independent, five is independent. 278 00:17:19,609 --> 00:17:21,079 Now, let's make the connection. 279 00:17:22,339 --> 00:17:24,880 Let's say Ford is the representative element. 280 00:17:26,599 --> 00:17:31,490 So in in previous approach, we have written like this four and five. 281 00:17:31,970 --> 00:17:34,250 And Ford is the representative element. 282 00:17:34,610 --> 00:17:40,700 So parent of five is basically Ford that everything will remain same. 283 00:17:41,990 --> 00:17:46,170 This will be one one one four, six and seven. 284 00:17:47,390 --> 00:17:48,800 Let's take one more example. 285 00:17:49,070 --> 00:17:54,410 We want to find the union of, let's say, six and seven. 286 00:17:55,250 --> 00:17:58,790 So seven parent of 77, parent of six is six. 287 00:17:59,030 --> 00:18:00,380 And we need to make them. 288 00:18:00,650 --> 00:18:07,330 So let's say we are doing like this, how it will look like inside. 289 00:18:08,450 --> 00:18:11,270 So I have six and seven, six as needed. 290 00:18:11,270 --> 00:18:14,530 Presenter development parent of seven is basically six. 291 00:18:14,540 --> 00:18:16,160 Everything else will remain same. 292 00:18:17,720 --> 00:18:18,470 This will be six. 293 00:18:18,470 --> 00:18:20,270 This will be four for one. 294 00:18:20,270 --> 00:18:20,720 When. 295 00:18:20,720 --> 00:18:21,050 When. 296 00:18:21,590 --> 00:18:24,470 Now let's take a union of five and six. 297 00:18:29,030 --> 00:18:30,620 So various firefighters here. 298 00:18:30,680 --> 00:18:33,710 So let me write like this, this is five. 299 00:18:34,300 --> 00:18:36,820 This is four and very six. 300 00:18:36,830 --> 00:18:37,820 So this is six. 301 00:18:38,400 --> 00:18:39,500 We are to combine them. 302 00:18:39,930 --> 00:18:46,760 Let's say I'm combining like this six and seven and how it will look like. 303 00:18:47,840 --> 00:18:54,390 So it will look like this four, five, six and seven and four is the representative element for this 304 00:18:54,390 --> 00:18:54,730 sector. 305 00:18:55,370 --> 00:19:03,050 And here the parent of six, parent of six is now for the parent of six is now for everything else, 306 00:19:03,050 --> 00:19:10,070 will remain same when one one four, four and six. 307 00:19:14,680 --> 00:19:17,350 Now we need to find out the union for. 308 00:19:21,070 --> 00:19:32,820 Three and seven, so various three threes here, two, then I have one, then I have three and seven. 309 00:19:33,190 --> 00:19:37,870 So this is seven, let's say four is the representative element. 310 00:19:38,440 --> 00:19:39,590 So this is six. 311 00:19:39,820 --> 00:19:40,420 This is. 312 00:19:41,350 --> 00:19:41,840 Seven. 313 00:19:41,890 --> 00:19:50,680 And this is five and how it will look like and said one, two, three, four, five, six and seven 314 00:19:50,950 --> 00:19:53,190 and four is the representative element. 315 00:19:53,560 --> 00:19:58,210 So here what I have done, I have changed the parent of one to four. 316 00:19:58,420 --> 00:20:02,120 So parent of one is for everything else will remain same. 317 00:20:02,410 --> 00:20:11,740 So one one four four four and six parent of two is one, parent of two is one. 318 00:20:12,190 --> 00:20:21,810 Parent of one is for a parent of one is for similarly parent of seven six. 319 00:20:21,820 --> 00:20:24,190 So parent of seven is six. 320 00:20:24,610 --> 00:20:26,080 Parent of five is four. 321 00:20:26,540 --> 00:20:28,810 Parent of five is four. 322 00:20:29,170 --> 00:20:31,000 Similarly parent of three is one. 323 00:20:31,180 --> 00:20:32,650 Parent of three is one. 324 00:20:33,310 --> 00:20:35,350 So that's how the court will look like. 325 00:20:35,920 --> 00:20:36,340 Right. 326 00:20:36,980 --> 00:20:39,040 That's how we can write the code for me. 327 00:20:39,040 --> 00:20:44,710 Exact function for me, exact function for fine function and for the union function. 328 00:20:45,520 --> 00:20:51,850 Now how this will help us, that's the main thing, how this will help us in cycle detection. 329 00:20:53,140 --> 00:20:55,330 Let's see how it will help us. 330 00:20:57,100 --> 00:21:00,400 So this is the problem that we have solved in our last video. 331 00:21:00,610 --> 00:21:03,370 Now let's see how this functions. 332 00:21:03,370 --> 00:21:06,610 Megg function, fine function and union function will help us here. 333 00:21:06,670 --> 00:21:12,180 So first of all, what we need to do, what we need to do, we need to call the function Miksad. 334 00:21:13,290 --> 00:21:13,570 Right. 335 00:21:14,370 --> 00:21:17,260 So let's call the function makes it so. 336 00:21:17,260 --> 00:21:18,670 I am writing like this. 337 00:21:22,170 --> 00:21:29,400 I'm calling the function makes it so this is not zero nor zero, not one or two or three, four, five, 338 00:21:29,400 --> 00:21:30,330 six, seven and eight. 339 00:21:30,630 --> 00:21:39,150 So make that function will do this three year old before this will be five. 340 00:21:40,070 --> 00:21:44,150 Six, seven and eight. 341 00:21:45,110 --> 00:21:49,790 This is the work of the Miksad function, second step, what was the second step? 342 00:21:49,790 --> 00:21:52,600 We need to pick the minimum wage and we need to combine them. 343 00:21:53,090 --> 00:21:54,440 So what is the minimum wage? 344 00:21:54,470 --> 00:21:57,100 I think this is the minimum wage for minimum wage. 345 00:21:57,230 --> 00:21:57,620 Eight. 346 00:21:58,010 --> 00:21:59,170 This is minimum wage. 347 00:21:59,480 --> 00:22:00,140 So what? 348 00:22:00,140 --> 00:22:02,150 Take seven, Vertex six. 349 00:22:03,650 --> 00:22:06,110 Vertex seven belongs to a different set. 350 00:22:06,540 --> 00:22:09,010 Vertex six belongs to Friend Said. 351 00:22:09,260 --> 00:22:10,510 So here, what will do? 352 00:22:10,520 --> 00:22:12,230 We will call the function union. 353 00:22:13,340 --> 00:22:13,910 Right. 354 00:22:14,330 --> 00:22:19,370 We will call the function union and how to check whether this is safe or not. 355 00:22:19,520 --> 00:22:26,300 Because the lie in different six belongs to the frenzied seven belongs to the friend said that means 356 00:22:26,510 --> 00:22:31,100 six belongs to different connected component, seven belongs to different connected company. 357 00:22:31,190 --> 00:22:35,630 OK, so one more thing that I want to tell you is C. 358 00:22:37,210 --> 00:22:37,990 This is. 359 00:22:39,200 --> 00:22:48,800 One connected component or one said this is another connected component or another set, if we want 360 00:22:48,800 --> 00:22:56,540 to combine them, if we want to connect one edge between them, then cycle will not be there. 361 00:22:57,620 --> 00:22:58,010 Right? 362 00:22:58,430 --> 00:23:00,050 This is one connected component. 363 00:23:00,110 --> 00:23:01,580 This is another connected component. 364 00:23:01,820 --> 00:23:04,780 And we are connecting with the help of this edge. 365 00:23:04,790 --> 00:23:08,390 We are connecting two different sets to different connected components. 366 00:23:08,630 --> 00:23:15,500 So the cycle will not be there if this is your one third when a critical component, this is yet another 367 00:23:15,500 --> 00:23:17,200 third, another connected component. 368 00:23:17,630 --> 00:23:27,560 If you do this, if you introduce edge in the elements which belong to the same set, then there will 369 00:23:27,560 --> 00:23:28,100 be cycles. 370 00:23:29,240 --> 00:23:31,010 So this is the concept of cycle. 371 00:23:32,060 --> 00:23:37,490 Cycle will not be there if you are connecting two different elements, the elements which belong to 372 00:23:37,490 --> 00:23:38,150 different set. 373 00:23:38,540 --> 00:23:40,880 So here I am doing cycle detection. 374 00:23:42,730 --> 00:23:43,090 S.. 375 00:23:44,150 --> 00:23:51,920 Seven belongs to a different connected component, six belongs to different connected component with 376 00:23:51,920 --> 00:23:57,860 the help of this edge, with the help of this age, I am connecting to sets. 377 00:23:58,190 --> 00:23:59,720 So cycle will not be there. 378 00:24:00,470 --> 00:24:02,180 So the cycle will not be there. 379 00:24:02,180 --> 00:24:03,500 And I can connect to them. 380 00:24:04,580 --> 00:24:05,720 I can connect them. 381 00:24:05,720 --> 00:24:07,310 So this will be six and seven. 382 00:24:07,310 --> 00:24:09,380 I will pick this age, mate. 383 00:24:09,740 --> 00:24:11,780 I will pick this edge rest. 384 00:24:11,780 --> 00:24:12,890 Everything will remain the same. 385 00:24:13,700 --> 00:24:14,150 It. 386 00:24:16,020 --> 00:24:18,630 Five, four. 387 00:24:19,820 --> 00:24:22,640 Two, one and zero. 388 00:24:24,970 --> 00:24:27,230 Now, what is the next minimum wage? 389 00:24:27,250 --> 00:24:33,300 I am running out of time, so what is the next minimum wage here next to minimum wages too? 390 00:24:33,340 --> 00:24:35,800 So too is present here, too, is present here. 391 00:24:35,810 --> 00:24:39,460 You can pick any one of them in any other time picking this one. 392 00:24:40,420 --> 00:24:40,840 Right. 393 00:24:41,110 --> 00:24:47,520 So it it belongs to different set to two, belongs to a different set. 394 00:24:47,800 --> 00:24:52,290 And this edge combines two different set or two different connected company. 395 00:24:52,450 --> 00:24:54,040 So Cycle will not be there. 396 00:24:54,050 --> 00:24:58,230 So let's connect them, let's pick this age and let's connect them. 397 00:24:58,930 --> 00:25:04,930 So I am picking this age and this will be to accommodate the rest. 398 00:25:04,930 --> 00:25:06,120 Everything will remain the same. 399 00:25:07,150 --> 00:25:08,950 This is six seven. 400 00:25:09,700 --> 00:25:10,810 This is five. 401 00:25:11,800 --> 00:25:12,910 This is four. 402 00:25:13,210 --> 00:25:17,170 I have picked up to two is here and this is one. 403 00:25:17,170 --> 00:25:18,090 And this is zero. 404 00:25:19,600 --> 00:25:22,420 What is the next minimum wage next to minimum wage to. 405 00:25:23,020 --> 00:25:26,290 So where six six is here. 406 00:25:26,590 --> 00:25:27,400 Where is five. 407 00:25:27,610 --> 00:25:28,570 Five is here. 408 00:25:28,810 --> 00:25:35,920 So six belongs to the friend said five belongs to defensed so connecting them will not create cycle, 409 00:25:37,090 --> 00:25:40,840 connecting them will not create a cycle so we can connect to them. 410 00:25:41,290 --> 00:25:44,350 So this will become five, six and seven. 411 00:25:44,620 --> 00:25:46,350 At least everything else will remain same. 412 00:25:47,740 --> 00:25:53,620 This is to create this is for this is one. 413 00:25:54,010 --> 00:25:55,180 This is zero. 414 00:25:57,810 --> 00:26:00,340 So what is the next minimum cycle after two? 415 00:26:00,360 --> 00:26:01,210 What do we have? 416 00:26:01,980 --> 00:26:03,080 I think we have four. 417 00:26:03,090 --> 00:26:04,130 So we have four here. 418 00:26:04,170 --> 00:26:05,070 We have four here. 419 00:26:05,340 --> 00:26:06,510 We can pick any age. 420 00:26:06,510 --> 00:26:08,910 For example, let's say I am starting with this one. 421 00:26:09,240 --> 00:26:12,000 So very zero zero is here. 422 00:26:12,120 --> 00:26:14,240 Where is when one is here. 423 00:26:14,550 --> 00:26:21,480 So they belong to different set, different connected component and joining them will not create a cycle. 424 00:26:21,660 --> 00:26:25,160 Joining them will not create a cycle so we can join them. 425 00:26:26,010 --> 00:26:27,060 So let's join them. 426 00:26:27,660 --> 00:26:29,790 This will be zero one arrest. 427 00:26:29,790 --> 00:26:31,260 Everything else will remain same. 428 00:26:32,350 --> 00:26:33,240 This is for. 429 00:26:34,460 --> 00:26:36,060 Five, six, seven. 430 00:26:37,160 --> 00:26:48,530 This is to come out now, the next minute is this one for so there two two is here, where is five? 431 00:26:48,860 --> 00:26:50,140 So five is here. 432 00:26:50,150 --> 00:26:53,330 So they belong to different sects. 433 00:26:53,360 --> 00:26:55,460 So connecting them will not create a cycle. 434 00:26:55,730 --> 00:26:57,000 So you can connect them. 435 00:26:57,440 --> 00:26:58,510 So let's connect them. 436 00:26:58,520 --> 00:27:03,560 This will be two, five, six, seven and eight. 437 00:27:04,010 --> 00:27:05,630 So I have picked this age. 438 00:27:08,690 --> 00:27:10,700 OK, I have picked this age. 439 00:27:12,300 --> 00:27:14,220 And everything else will remain the same. 440 00:27:14,430 --> 00:27:23,170 So this is for this is zero comma one now what is the next minimum wage? 441 00:27:23,520 --> 00:27:25,340 So after all, what do we have? 442 00:27:25,350 --> 00:27:27,420 I think we have six, right? 443 00:27:27,880 --> 00:27:32,250 We have six so far, six where it lies. 444 00:27:32,760 --> 00:27:34,230 So it is present here. 445 00:27:34,650 --> 00:27:36,180 Where is six? 446 00:27:36,880 --> 00:27:38,760 So six is also present here. 447 00:27:38,760 --> 00:27:41,130 See eight and six. 448 00:27:41,760 --> 00:27:45,790 Both elements, both vertex, lie in the same set. 449 00:27:46,140 --> 00:27:48,690 So taking this will create a cycle. 450 00:27:49,890 --> 00:27:51,000 I'm repeating myself. 451 00:27:52,260 --> 00:27:58,770 Eight and six belong to the same set, belong to the same connected component. 452 00:27:59,580 --> 00:28:02,520 So picking this edge will create a cycle. 453 00:28:02,850 --> 00:28:03,900 How it will create cycle. 454 00:28:03,900 --> 00:28:07,290 You can see this one, this one, this one and this one. 455 00:28:07,290 --> 00:28:08,130 They will be cycle. 456 00:28:08,370 --> 00:28:09,600 So you cannot pick them. 457 00:28:09,600 --> 00:28:11,820 Right, because six and eight belong to the same set. 458 00:28:12,180 --> 00:28:13,540 So he cannot pick six. 459 00:28:13,980 --> 00:28:18,150 Now let's move on to the next with next to it is I think seven. 460 00:28:18,720 --> 00:28:19,200 Right. 461 00:28:19,200 --> 00:28:22,320 I have seven here and I have seven here. 462 00:28:22,740 --> 00:28:27,180 So let's check where those eight lies. 463 00:28:27,180 --> 00:28:30,600 So eight is present here where those seven lies. 464 00:28:30,600 --> 00:28:32,010 Seven is also present here. 465 00:28:32,280 --> 00:28:32,760 Right. 466 00:28:32,760 --> 00:28:35,580 Again, same set element belong to the same set. 467 00:28:35,790 --> 00:28:38,670 So you cannot pick this because it will create a cycle. 468 00:28:39,270 --> 00:28:41,100 Let's talk about this seven now. 469 00:28:41,700 --> 00:28:46,280 So where does to present to is present here. 470 00:28:47,440 --> 00:28:48,180 Various three. 471 00:28:48,180 --> 00:28:50,550 Present three. 472 00:28:52,370 --> 00:28:56,960 OK, we're sorry, OK, sorry, I basically forgot to write three here. 473 00:29:00,850 --> 00:29:03,790 I forgot to write to you, so sorry, please forgive me. 474 00:29:10,720 --> 00:29:11,410 So let's start. 475 00:29:11,440 --> 00:29:18,350 So I was saying to is present here and trees present here, they belong to different set, different 476 00:29:18,350 --> 00:29:24,190 set means, different connected component, and we are connecting to different connected components. 477 00:29:24,190 --> 00:29:25,500 So cycle will not be there. 478 00:29:26,140 --> 00:29:27,670 So we can pick this. 479 00:29:28,930 --> 00:29:32,600 So this will become let's connect three here. 480 00:29:32,650 --> 00:29:39,520 So this will be two, three, five, six, seven and eight and everything else will remain the same. 481 00:29:40,300 --> 00:29:43,770 So this will be four and this will be zero seven. 482 00:29:45,460 --> 00:29:47,750 Now let's pick the next minimum wage. 483 00:29:47,890 --> 00:29:49,760 So after seven, I think I have eight. 484 00:29:49,780 --> 00:29:50,910 So it is present here. 485 00:29:51,130 --> 00:29:52,230 It is present here. 486 00:29:52,600 --> 00:29:54,250 So let's pick in any order. 487 00:29:54,250 --> 00:29:55,510 Let's say I'm picking this one. 488 00:29:55,900 --> 00:29:59,860 So very zero zero seven zero is here in this area. 489 00:29:59,900 --> 00:30:01,560 Seven seven is in the set. 490 00:30:01,570 --> 00:30:02,700 So we can take this edge. 491 00:30:03,280 --> 00:30:05,170 So let's take this edge. 492 00:30:05,620 --> 00:30:06,010 Right. 493 00:30:06,430 --> 00:30:13,150 So I'm writing here, let's combine desert, certain desert, because euro is present here and the seven 494 00:30:13,150 --> 00:30:13,790 is present here. 495 00:30:13,810 --> 00:30:16,020 So connecting them will not create a cycle. 496 00:30:16,420 --> 00:30:23,670 So this will be zero, comma one, then two, three, five, six, seven and eight. 497 00:30:24,310 --> 00:30:31,030 And I have selected this edge and four will remain same rate. 498 00:30:32,530 --> 00:30:34,720 We have four, so four will remain same. 499 00:30:36,190 --> 00:30:38,520 Now let's pick the next minimum. 500 00:30:39,610 --> 00:30:40,720 So which is this one. 501 00:30:41,080 --> 00:30:41,440 Eight. 502 00:30:41,560 --> 00:30:42,190 So one. 503 00:30:42,460 --> 00:30:43,120 Where is one. 504 00:30:43,120 --> 00:30:45,220 Where is two, one and two. 505 00:30:45,400 --> 00:30:46,680 The present in the same side. 506 00:30:46,720 --> 00:30:49,660 So you cannot pick this because it will create a cycle. 507 00:30:50,110 --> 00:30:51,220 How it will create a cycle. 508 00:30:51,220 --> 00:31:02,980 You can see this one then, then basically this, then this, then this, then this and then this cycle 509 00:31:02,980 --> 00:31:03,700 will be created. 510 00:31:03,970 --> 00:31:05,110 So it cannot pick this. 511 00:31:05,950 --> 00:31:08,050 Now after eight, what is the next minimum? 512 00:31:08,050 --> 00:31:10,630 Next medium is, I think nine. 513 00:31:11,320 --> 00:31:11,710 Right. 514 00:31:11,950 --> 00:31:14,800 So three and four, they belong to different set. 515 00:31:15,340 --> 00:31:17,230 So three is here for is here. 516 00:31:17,860 --> 00:31:19,030 They belong to different set. 517 00:31:19,420 --> 00:31:24,160 So connecting them will not create a cycle so you can connect them. 518 00:31:25,740 --> 00:31:30,760 Zero one, two, three, four, five, six, seven and eight. 519 00:31:31,940 --> 00:31:34,820 Right, so you have connected them after nine. 520 00:31:36,590 --> 00:31:38,250 So after nine, what is the next minimum? 521 00:31:39,080 --> 00:31:47,990 I think this has been so for 10, four and five, so zero five zero, you cannot pick this next after 522 00:31:47,990 --> 00:31:49,910 10, we have 11 so far. 523 00:31:49,910 --> 00:31:51,370 Eleven one and seven. 524 00:31:51,680 --> 00:31:53,360 So when is it seven is here. 525 00:31:53,370 --> 00:31:54,520 You cannot pick this. 526 00:31:55,430 --> 00:31:58,490 So now 14 so far, 14, three and five. 527 00:31:58,730 --> 00:31:59,690 So threes here. 528 00:31:59,690 --> 00:32:00,440 Five is here. 529 00:32:00,440 --> 00:32:02,750 You cannot pick this and that's it. 530 00:32:03,170 --> 00:32:07,190 We come to the end of the algorithm and what do we have. 531 00:32:07,520 --> 00:32:09,410 We have one set. 532 00:32:10,640 --> 00:32:14,480 One set means one connected component. 533 00:32:14,810 --> 00:32:16,910 And what is that one connected component. 534 00:32:17,330 --> 00:32:21,170 That one connected component is basically from zero. 535 00:32:21,860 --> 00:32:27,800 I have one I have seven six, five 536 00:32:30,620 --> 00:32:36,890 to eight, three and four. 537 00:32:37,670 --> 00:32:38,150 Right. 538 00:32:38,720 --> 00:32:44,990 So that's how that disjoint set will help us in cycle detection encryption algorithm. 539 00:32:45,650 --> 00:32:51,590 So I hope you have understood the complete algorithm, complete disjoint how this disjoined is working 540 00:32:51,590 --> 00:32:52,580 during is working. 541 00:32:52,580 --> 00:33:00,530 First of all, why did we call the function Miksad on all the vertices then what we are doing, we are 542 00:33:00,530 --> 00:33:03,860 calling the union function and we are calling for end function. 543 00:33:04,220 --> 00:33:06,740 Basically union function is calling finde function. 544 00:33:06,980 --> 00:33:07,430 Right. 545 00:33:08,870 --> 00:33:14,420 So I hope you have understood completely and now you have also understood what is the why. 546 00:33:14,420 --> 00:33:15,850 I'm saying certain components. 547 00:33:15,890 --> 00:33:17,690 Same because they are saying. 548 00:33:18,850 --> 00:33:26,380 Right, so if to eliminate lies in the same set, that means they will lie in the same connected component, 549 00:33:26,470 --> 00:33:30,010 that means cycle will be there, right? 550 00:33:30,250 --> 00:33:32,500 So what is the final conclusion? 551 00:33:32,830 --> 00:33:42,850 Final conclusion is if the element lies in the same set, same set or connected component one and the 552 00:33:42,850 --> 00:33:51,670 same thing, then there will be cycle else, no cycle else no cycle, because they lie in different 553 00:33:51,670 --> 00:33:59,290 set, because they lie in different set and you are connecting two different sets or two different connected 554 00:33:59,290 --> 00:33:59,860 components. 555 00:34:00,160 --> 00:34:03,750 So this edge, this edge will not create a cycle. 556 00:34:04,060 --> 00:34:05,770 So that is the complete algorithm. 557 00:34:05,920 --> 00:34:07,450 So in next we do what I will do. 558 00:34:07,450 --> 00:34:10,100 I will write the code for the Kruskal algorithm. 559 00:34:11,020 --> 00:34:12,670 So this is it from this video. 560 00:34:12,679 --> 00:34:17,800 Guys, if you have any doubt, I know this this algorithm is a little bit complex at first. 561 00:34:18,159 --> 00:34:20,230 You will face like few challenges. 562 00:34:20,230 --> 00:34:22,210 You will find it difficult to digest. 563 00:34:22,210 --> 00:34:27,940 But after watching the video once or twice, after going to the corridor after after training these 564 00:34:27,940 --> 00:34:30,850 examples, you will be able to understand it very easily. 565 00:34:30,880 --> 00:34:33,040 This is very, very simple overtime rate. 566 00:34:33,880 --> 00:34:38,710 So since we have learned anything, we have learned, Disjoined said we have learned three functions, 567 00:34:38,710 --> 00:34:40,659 makes that final function union function. 568 00:34:40,900 --> 00:34:42,250 We have learned a crucial algorithm. 569 00:34:42,250 --> 00:34:44,469 So it's a lot of things that we are learning at once. 570 00:34:44,679 --> 00:34:48,290 But after like some time after one or two, that it will sink in. 571 00:34:48,760 --> 00:34:50,110 So and next we do what I will do. 572 00:34:50,110 --> 00:34:52,630 I will write very simple code for I'm still worried. 573 00:34:52,630 --> 00:34:55,929 I'm sorry for Koskela algorithm for finding Misti. 574 00:34:56,170 --> 00:34:57,370 So this is it from this video. 575 00:34:57,370 --> 00:34:59,160 Guys, I will see you in the next one. 576 00:34:59,320 --> 00:34:59,890 Thank you.