1
00:00:00,540 --> 00:00:02,760
Hi, everyone, welcome to this new video.

2
00:00:02,940 --> 00:00:09,210
So in this video, we are going to write the code for this problem, Commutable Island and end this

3
00:00:09,210 --> 00:00:09,570
problem.

4
00:00:09,570 --> 00:00:15,240
But we need to do we need to write the code for finding out the minimum spending tree, for finding

5
00:00:15,240 --> 00:00:16,270
out a spending tree.

6
00:00:16,320 --> 00:00:18,060
We have discussed 12 Erdem.

7
00:00:18,090 --> 00:00:20,340
One is Krischan, either one is Prem's.

8
00:00:20,610 --> 00:00:23,460
So I'm going to write the code of acoustical algorithm.

9
00:00:23,460 --> 00:00:29,970
And there are two reasons because it is very easy to implement and also very fast to implement, because

10
00:00:29,970 --> 00:00:35,720
focus algorithm, we already know the code for these two functions makes that function fine function.

11
00:00:35,730 --> 00:00:39,630
So we already know and already remember the code for these to function.

12
00:00:39,810 --> 00:00:43,870
So that's a critical algorithm is very easy and very fast to implement.

13
00:00:44,760 --> 00:00:47,770
One more thing is basically in the edges area.

14
00:00:47,850 --> 00:00:53,430
The first is basically we have source node, second one is destination node and the third is basically

15
00:00:53,700 --> 00:00:54,390
Yorvit.

16
00:00:55,530 --> 00:00:55,970
Right.

17
00:00:56,160 --> 00:01:04,920
So what I want to say here is so if we can see here, the first one is the source, second one is the

18
00:01:04,920 --> 00:01:08,950
destination vertex and third one is basically the or I can say cost.

19
00:01:09,270 --> 00:01:15,840
One more thing to notice here is if the number of islands are basically four, if the number of islands

20
00:01:15,840 --> 00:01:22,470
are basically N, then the labeling of the island starts from one one to end and not from zero two and

21
00:01:22,470 --> 00:01:23,210
minus one.

22
00:01:23,220 --> 00:01:23,620
Right.

23
00:01:23,850 --> 00:01:27,170
So here we can see if the number of islands are four.

24
00:01:27,180 --> 00:01:30,890
Then I have labelling one, two, three and four.

25
00:01:31,020 --> 00:01:37,440
So labeling are in this manner one to one and not zero two and minus one that we typically see in other

26
00:01:37,440 --> 00:01:37,980
problems.

27
00:01:38,340 --> 00:01:38,730
Right.

28
00:01:38,910 --> 00:01:42,000
So the indexing is one based and not zero based.

29
00:01:43,380 --> 00:01:44,440
So we know everything.

30
00:01:44,460 --> 00:01:47,180
Now let's start writing the code for this problem.

31
00:01:48,030 --> 00:01:53,490
So this is the function that we need to complete.

32
00:01:53,820 --> 00:01:56,490
So first of all, let's change the variable name.

33
00:01:56,500 --> 00:01:58,020
So N is the number of islands.

34
00:01:58,380 --> 00:02:03,740
And second is basically this is the edges at a rate, the total number of edges, edges area.

35
00:02:04,530 --> 00:02:08,900
So we are going to implement them for our algorithm.

36
00:02:09,630 --> 00:02:13,020
So first of all, let us write the function.

37
00:02:13,020 --> 00:02:18,180
Miksad So we remember the code for Miksad function.

38
00:02:18,180 --> 00:02:22,290
What it does is it simply iterate so I equals one.

39
00:02:22,890 --> 00:02:30,240
I will start from one and not zero because the labelling are one indexed based and what it does is it

40
00:02:30,240 --> 00:02:33,840
simply does variant of i.e. equals I.

41
00:02:34,050 --> 00:02:40,740
This is the code for Miksad function, so Miksad function will take and as input and it will take Birendra

42
00:02:40,740 --> 00:02:41,340
as input.

43
00:02:41,580 --> 00:02:49,800
So n the number of filings and it will also take the parent derrieres input, find the next function

44
00:02:49,800 --> 00:02:53,580
that we are going to write is basically defined function.

45
00:02:54,510 --> 00:02:59,130
So well defined function does it returns the present development for the set.

46
00:02:59,670 --> 00:03:01,800
And what is the code for doing that.

47
00:03:01,830 --> 00:03:10,770
That is pretty much that we already remember while parent of A is not equal to i.e. what we do i.e.

48
00:03:10,770 --> 00:03:16,590
equals behrendorff i.e. and return EI.

49
00:03:17,490 --> 00:03:22,920
So this is the code for defined function that we have already discussed many times and what this final

50
00:03:22,920 --> 00:03:24,330
function will take as input.

51
00:03:24,480 --> 00:03:29,720
It will take a and it will take the parent bearing.

52
00:03:30,180 --> 00:03:32,130
So it is going to take two things.

53
00:03:32,880 --> 00:03:39,570
First, Vertex and we are going to return the representative element for that set rate.

54
00:03:40,080 --> 00:03:41,580
So spelling is wrong here.

55
00:03:41,770 --> 00:03:43,320
It should be, period.

56
00:03:44,190 --> 00:03:46,820
So we know the code for make certain finds it.

57
00:03:46,860 --> 00:03:50,000
And let's talk about this.

58
00:03:50,010 --> 00:03:51,090
So what we need to do.

59
00:03:51,210 --> 00:03:55,110
So in Kruskal algorithm, the first step is basically start.

60
00:03:55,950 --> 00:04:03,330
We basically sort the edges, according to David, so we have solid function.

61
00:04:03,960 --> 00:04:09,780
So start function will take edges that begin edges not.

62
00:04:09,810 --> 00:04:13,140
And so what is the first step?

63
00:04:13,140 --> 00:04:15,280
First step is basically increase.

64
00:04:15,390 --> 00:04:25,530
Coloradoan first step is basically starting edges on basis of which we need to sort ideas on the basis

65
00:04:25,530 --> 00:04:26,010
of it.

66
00:04:26,490 --> 00:04:28,230
So this court is currently wrong.

67
00:04:28,230 --> 00:04:33,630
This code is not starting edges on the basis of it, but they will come to this code a little bit later.

68
00:04:33,990 --> 00:04:35,550
Let's do the rest of the thing first.

69
00:04:35,760 --> 00:04:43,050
So what we to do, we need to call the function, mix it and Miksad function to experience that as input.

70
00:04:43,680 --> 00:04:45,090
So be it.

71
00:04:45,090 --> 00:04:49,470
And what will be the size of barratry and plus one.

72
00:04:49,470 --> 00:04:55,230
Right, because the indexing starts from one and we are going to call the function Miksad.

73
00:04:55,740 --> 00:04:59,600
It will take number island and it will take your parent very.

74
00:05:00,590 --> 00:05:08,450
Fine, now, what else do we need to do so we need to return the minimum cost, initially the cost is

75
00:05:08,480 --> 00:05:14,320
zero and in the end, the next step in question, Legatum, is we need to trade over the edges.

76
00:05:14,750 --> 00:05:17,740
So let's start our trading over the edges one by one.

77
00:05:18,800 --> 00:05:26,580
So I just dot says I placeless, so I'm going to trade over the edges.

78
00:05:26,720 --> 00:05:28,400
So what is the source of our text?

79
00:05:29,390 --> 00:05:35,140
So Susan overtaxes edges of a and first element that is zero index.

80
00:05:35,780 --> 00:05:45,620
What is the destination vertex destination where Texas edges of a and when now where they need to do

81
00:05:45,620 --> 00:05:51,390
we need to detect whether the cycle will be created when we join the source vertex investigation vertex

82
00:05:51,390 --> 00:05:56,480
take some not so far cycle detection, but we need to do we need to call the function Batan.

83
00:05:56,510 --> 00:06:05,270
So let's say this is the representative, a representative element for S that is the source for text.

84
00:06:05,570 --> 00:06:07,280
So who is the representative element?

85
00:06:08,310 --> 00:06:14,330
So for finding out the representative element, we will call the function find I will give.

86
00:06:14,330 --> 00:06:17,480
So Vertex and I will give Birand very

87
00:06:19,910 --> 00:06:25,120
similarly who is the representative element for Destination Vertex?

88
00:06:25,730 --> 00:06:31,490
So, you know, to call find the function to give destination Vertex and the parent data.

89
00:06:32,720 --> 00:06:37,330
So here what they need to do, we need to detect whether there is a cycle or not.

90
00:06:37,970 --> 00:06:47,750
So if that represents element for those, vertex is not equal to the representative element for destination

91
00:06:47,750 --> 00:06:51,830
vertex, that means normal cycle cycle is not there.

92
00:06:51,840 --> 00:06:53,900
That means we can connect these two edges.

93
00:06:54,170 --> 00:07:04,790
So if we are connecting these two edges, my cost will be increased by edges of EI and cost is presenting

94
00:07:05,150 --> 00:07:06,770
at indexed to rate.

95
00:07:08,300 --> 00:07:11,150
And what we need to do, we need to take a union of them.

96
00:07:11,150 --> 00:07:12,020
And what is done.

97
00:07:12,020 --> 00:07:21,530
Union union is nothing but behrendorff representative Orris is equal to are the representative element

98
00:07:21,530 --> 00:07:22,820
for destination vertex.

99
00:07:23,180 --> 00:07:25,430
You can do the opposite for this, right.

100
00:07:25,550 --> 00:07:26,990
You can do opposite also.

101
00:07:26,990 --> 00:07:35,180
That is you can also write behrendorff representative element of the is a to ah as you can do this also

102
00:07:35,420 --> 00:07:38,270
so it doesn't matter, you can write any one of them.

103
00:07:38,780 --> 00:07:40,250
So let's remove this.

104
00:07:40,280 --> 00:07:40,610
Right.

105
00:07:40,640 --> 00:07:41,480
I'm writing this.

106
00:07:41,480 --> 00:07:43,420
So this is what this is union.

107
00:07:44,750 --> 00:07:46,070
This is union function.

108
00:07:47,210 --> 00:07:47,630
Right.

109
00:07:47,750 --> 00:07:55,790
And finally what they are going to do is you are going to return the cost, you are going to return

110
00:07:55,790 --> 00:07:56,710
the cost.

111
00:07:57,110 --> 00:08:03,230
So let me try to explain you first step is basically you need to sort the ideas on basis of which I

112
00:08:03,230 --> 00:08:04,280
am sorting the edges.

113
00:08:04,280 --> 00:08:07,940
But this sorehead function is not starting on the basis of it.

114
00:08:08,270 --> 00:08:09,350
So we will do something.

115
00:08:09,350 --> 00:08:11,760
But let's not talk about this now.

116
00:08:11,930 --> 00:08:16,790
Next step is basically we need to call the function, make certain every element, every vertex.

117
00:08:17,030 --> 00:08:22,480
So I am calling the function makes it and we need to return the minimum cost.

118
00:08:22,490 --> 00:08:25,100
So initially the cost is zero and increase.

119
00:08:25,700 --> 00:08:31,790
The next step is basically you need to pick edges one by one right here to pick this sorted edges one

120
00:08:31,790 --> 00:08:32,210
by one.

121
00:08:32,330 --> 00:08:34,460
So I'm picking the sorted edges one by one.

122
00:08:34,549 --> 00:08:37,520
So I am picking one vertex and either vertex.

123
00:08:37,970 --> 00:08:43,159
Then I am finding out who is the representative element for this vertex and who is the representative

124
00:08:43,159 --> 00:08:44,780
element for the destination vertex.

125
00:08:45,080 --> 00:08:50,690
If the representative elements are different, different means connecting them will not create cycle,

126
00:08:51,140 --> 00:08:51,620
right.

127
00:08:51,620 --> 00:08:52,790
So we can connect them.

128
00:08:52,970 --> 00:08:55,330
So I am connecting them right.

129
00:08:55,340 --> 00:09:00,620
This is union and since we are connecting them, so we need to take the cost of that also.

130
00:09:00,830 --> 00:09:03,800
So I am adding the cost and then I am returning the cost.

131
00:09:03,980 --> 00:09:09,470
Now the only thing remaining is basically how we can sort the ideas on the basis of it.

132
00:09:09,470 --> 00:09:11,990
So it's pretty simple what you need to do.

133
00:09:12,260 --> 00:09:19,340
So this sort function, what it takes, it takes third parameter and third parameter is your compare

134
00:09:19,340 --> 00:09:23,320
function on what basis you want to compare your element.

135
00:09:24,200 --> 00:09:31,310
So this is how you write bool return type will be bool compare function, but this compare function

136
00:09:31,310 --> 00:09:31,850
will take.

137
00:09:32,030 --> 00:09:35,480
So it will take this vector of integers.

138
00:09:36,470 --> 00:09:36,890
Right.

139
00:09:37,130 --> 00:09:40,670
So this compare function will take vector of integers.

140
00:09:41,060 --> 00:09:47,960
Let's say the first vector is a first element and the second element is let's be.

141
00:09:48,650 --> 00:09:50,930
So on what basis do you want to start.

142
00:09:51,170 --> 00:09:53,270
I want to start on the basis of that.

143
00:09:53,660 --> 00:09:59,270
The second value that is the cost should be less than the second value of.

144
00:09:59,690 --> 00:10:03,800
Another vector, so that's how you can start on the basis of it.

145
00:10:04,110 --> 00:10:06,410
So let me try to explain you again.

146
00:10:06,750 --> 00:10:10,350
So this sort function, it takes third parameter.

147
00:10:10,470 --> 00:10:15,180
Third parameter is your computer function and this compare function that it will be.

148
00:10:15,540 --> 00:10:20,250
This is actually this code is specific to C++ in Java.

149
00:10:20,250 --> 00:10:22,310
You will have something again similar to this.

150
00:10:22,320 --> 00:10:25,660
Similarly for Python, you will have modification of Saat function.

151
00:10:25,830 --> 00:10:31,080
So this code is like I can say, this is something specific to C++.

152
00:10:31,110 --> 00:10:32,610
So what this art function takes.

153
00:10:33,280 --> 00:10:39,310
Oh, sorry, but this computer function takes compare function takes two elements that you will compare.

154
00:10:39,510 --> 00:10:46,800
So I am calling certain edges and what is I just contain it contains vector integer so that I am passing

155
00:10:46,800 --> 00:10:47,720
vector integers.

156
00:10:48,060 --> 00:10:53,930
So I have two integers, two veteran teachers E and B and I want to start on the basis of it.

157
00:10:54,240 --> 00:10:56,340
So I am starting on the basis of which.

158
00:10:57,030 --> 00:10:57,470
Right.

159
00:10:58,380 --> 00:11:02,900
So our edges array will now be sorted on basis of weight.

160
00:11:03,480 --> 00:11:07,240
So you can do a similar thing, very similar thing and other languages also.

161
00:11:07,380 --> 00:11:13,190
So this thing is easily available in other programming languages also.

162
00:11:13,440 --> 00:11:17,840
So that I think we are then our code should work.

163
00:11:18,420 --> 00:11:19,740
So yep.

164
00:11:19,740 --> 00:11:22,230
Let's try to test our code and then we will.

165
00:11:24,870 --> 00:11:25,230
Yeah.

166
00:11:25,230 --> 00:11:28,520
So our code passes the basic test cases.

167
00:11:28,890 --> 00:11:31,860
Now let's run our code for all the test cases.

168
00:11:33,330 --> 00:11:37,010
So is it stuck or something.

169
00:11:43,790 --> 00:11:53,000
Yeah, so, yes, our court is working fine now, right, our court is working and let me again quickly

170
00:11:53,000 --> 00:11:57,440
go through the whole court so we already know the court for Miksad function.

171
00:11:57,660 --> 00:11:59,090
We have already discussed this.

172
00:11:59,330 --> 00:12:01,670
We already know the court for finds that function again.

173
00:12:01,670 --> 00:12:02,870
We have already discussed this.

174
00:12:03,200 --> 00:12:07,610
Then, of course, Coloradoan, very simple sort on the basis of which I am starting on the basis of

175
00:12:07,610 --> 00:12:07,910
it.

176
00:12:08,270 --> 00:12:12,200
And this is how you can start on the basis of it, then it's very simple.

177
00:12:12,530 --> 00:12:14,690
Called the third function ideato.

178
00:12:14,690 --> 00:12:20,810
The court alleges you'll find out the source vertex destination vertex and then what you need to do

179
00:12:21,080 --> 00:12:22,900
to find out the representative element.

180
00:12:22,940 --> 00:12:23,330
Right.

181
00:12:24,240 --> 00:12:28,490
If the representative elements are different, they belong to the different set, different connected

182
00:12:28,490 --> 00:12:29,000
components.

183
00:12:29,210 --> 00:12:33,590
So connecting them that is taking union of them will not create a cycle in our graph.

184
00:12:33,950 --> 00:12:35,360
So that's why you can take them.

185
00:12:35,360 --> 00:12:37,910
If I am taking it, then I need to add that cost.

186
00:12:37,910 --> 00:12:39,680
And finally I'm returning the cost.

187
00:12:39,690 --> 00:12:41,620
That's very, very simple.

188
00:12:41,640 --> 00:12:42,200
All right.

189
00:12:43,100 --> 00:12:47,270
So that's why I said that Kruskal algorithm is highly recommended.

190
00:12:47,540 --> 00:12:54,170
So whenever you encounter a problem, a problem and you have to option curriculum's always try to go

191
00:12:54,170 --> 00:12:59,600
for the Google algorithm because it is very simple and very fast to implement rate.

192
00:13:00,630 --> 00:13:01,770
So that said, guys.

193
00:13:03,020 --> 00:13:07,310
That is all that I want to discuss in this video, so I will see you in the next one.

194
00:13:07,400 --> 00:13:08,060
Thank you.