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.

