Hi, everyone, welcome to this new video.
So in this video, we are going to write the code for this problem, Commutable Island and end this
problem.
But we need to do we need to write the code for finding out the minimum spending tree, for finding
out a spending tree.
We have discussed 12 Erdem.
One is Krischan, either one is Prem's.
So I'm going to write the code of acoustical algorithm.
And there are two reasons because it is very easy to implement and also very fast to implement, because
focus algorithm, we already know the code for these two functions makes that function fine function.
So we already know and already remember the code for these to function.
So that's a critical algorithm is very easy and very fast to implement.
One more thing is basically in the edges area.
The first is basically we have source node, second one is destination node and the third is basically
Yorvit.
Right.
So what I want to say here is so if we can see here, the first one is the source, second one is the
destination vertex and third one is basically the or I can say cost.
One more thing to notice here is if the number of islands are basically four, if the number of islands
are basically N, then the labeling of the island starts from one one to end and not from zero two and
minus one.
Right.
So here we can see if the number of islands are four.
Then I have labelling one, two, three and four.
So labeling are in this manner one to one and not zero two and minus one that we typically see in other
problems.
Right.
So the indexing is one based and not zero based.
So we know everything.
Now let's start writing the code for this problem.
So this is the function that we need to complete.
So first of all, let's change the variable name.
So N is the number of islands.
And second is basically this is the edges at a rate, the total number of edges, edges area.
So we are going to implement them for our algorithm.
So first of all, let us write the function.
Miksad So we remember the code for Miksad function.
What it does is it simply iterate so I equals one.
I will start from one and not zero because the labelling are one indexed based and what it does is it
simply does variant of i.e. equals I.
This is the code for Miksad function, so Miksad function will take and as input and it will take Birendra
as input.
So n the number of filings and it will also take the parent derrieres input, find the next function
that we are going to write is basically defined function.
So well defined function does it returns the present development for the set.
And what is the code for doing that.
That is pretty much that we already remember while parent of A is not equal to i.e. what we do i.e.
equals behrendorff i.e. and return EI.
So this is the code for defined function that we have already discussed many times and what this final
function will take as input.
It will take a and it will take the parent bearing.
So it is going to take two things.
First, Vertex and we are going to return the representative element for that set rate.
So spelling is wrong here.
It should be, period.
So we know the code for make certain finds it.
And let's talk about this.
So what we need to do.
So in Kruskal algorithm, the first step is basically start.
We basically sort the edges, according to David, so we have solid function.
So start function will take edges that begin edges not.
And so what is the first step?
First step is basically increase.
Coloradoan first step is basically starting edges on basis of which we need to sort ideas on the basis
of it.
So this court is currently wrong.
This code is not starting edges on the basis of it, but they will come to this code a little bit later.
Let's do the rest of the thing first.
So what we to do, we need to call the function, mix it and Miksad function to experience that as input.
So be it.
And what will be the size of barratry and plus one.
Right, because the indexing starts from one and we are going to call the function Miksad.
It will take number island and it will take your parent very.
Fine, now, what else do we need to do so we need to return the minimum cost, initially the cost is
zero and in the end, the next step in question, Legatum, is we need to trade over the edges.
So let's start our trading over the edges one by one.
So I just dot says I placeless, so I'm going to trade over the edges.
So what is the source of our text?
So Susan overtaxes edges of a and first element that is zero index.
What is the destination vertex destination where Texas edges of a and when now where they need to do
we need to detect whether the cycle will be created when we join the source vertex investigation vertex
take some not so far cycle detection, but we need to do we need to call the function Batan.
So let's say this is the representative, a representative element for S that is the source for text.
So who is the representative element?
So for finding out the representative element, we will call the function find I will give.
So Vertex and I will give Birand very
similarly who is the representative element for Destination Vertex?
So, you know, to call find the function to give destination Vertex and the parent data.
So here what they need to do, we need to detect whether there is a cycle or not.
So if that represents element for those, vertex is not equal to the representative element for destination
vertex, that means normal cycle cycle is not there.
That means we can connect these two edges.
So if we are connecting these two edges, my cost will be increased by edges of EI and cost is presenting
at indexed to rate.
And what we need to do, we need to take a union of them.
And what is done.
Union union is nothing but behrendorff representative Orris is equal to are the representative element
for destination vertex.
You can do the opposite for this, right.
You can do opposite also.
That is you can also write behrendorff representative element of the is a to ah as you can do this also
so it doesn't matter, you can write any one of them.
So let's remove this.
Right.
I'm writing this.
So this is what this is union.
This is union function.
Right.
And finally what they are going to do is you are going to return the cost, you are going to return
the cost.
So let me try to explain you first step is basically you need to sort the ideas on basis of which I
am sorting the edges.
But this sorehead function is not starting on the basis of it.
So we will do something.
But let's not talk about this now.
Next step is basically we need to call the function, make certain every element, every vertex.
So I am calling the function makes it and we need to return the minimum cost.
So initially the cost is zero and increase.
The next step is basically you need to pick edges one by one right here to pick this sorted edges one
by one.
So I'm picking the sorted edges one by one.
So I am picking one vertex and either vertex.
Then I am finding out who is the representative element for this vertex and who is the representative
element for the destination vertex.
If the representative elements are different, different means connecting them will not create cycle,
right.
So we can connect them.
So I am connecting them right.
This is union and since we are connecting them, so we need to take the cost of that also.
So I am adding the cost and then I am returning the cost.
Now the only thing remaining is basically how we can sort the ideas on the basis of it.
So it's pretty simple what you need to do.
So this sort function, what it takes, it takes third parameter and third parameter is your compare
function on what basis you want to compare your element.
So this is how you write bool return type will be bool compare function, but this compare function
will take.
So it will take this vector of integers.
Right.
So this compare function will take vector of integers.
Let's say the first vector is a first element and the second element is let's be.
So on what basis do you want to start.
I want to start on the basis of that.
The second value that is the cost should be less than the second value of.
Another vector, so that's how you can start on the basis of it.
So let me try to explain you again.
So this sort function, it takes third parameter.
Third parameter is your computer function and this compare function that it will be.
This is actually this code is specific to C++ in Java.
You will have something again similar to this.
Similarly for Python, you will have modification of Saat function.
So this code is like I can say, this is something specific to C++.
So what this art function takes.
Oh, sorry, but this computer function takes compare function takes two elements that you will compare.
So I am calling certain edges and what is I just contain it contains vector integer so that I am passing
vector integers.
So I have two integers, two veteran teachers E and B and I want to start on the basis of it.
So I am starting on the basis of which.
Right.
So our edges array will now be sorted on basis of weight.
So you can do a similar thing, very similar thing and other languages also.
So this thing is easily available in other programming languages also.
So that I think we are then our code should work.
So yep.
Let's try to test our code and then we will.
Yeah.
So our code passes the basic test cases.
Now let's run our code for all the test cases.
So is it stuck or something.
Yeah, so, yes, our court is working fine now, right, our court is working and let me again quickly
go through the whole court so we already know the court for Miksad function.
We have already discussed this.
We already know the court for finds that function again.
We have already discussed this.
Then, of course, Coloradoan, very simple sort on the basis of which I am starting on the basis of
it.
And this is how you can start on the basis of it, then it's very simple.
Called the third function ideato.
The court alleges you'll find out the source vertex destination vertex and then what you need to do
to find out the representative element.
Right.
If the representative elements are different, they belong to the different set, different connected
components.
So connecting them that is taking union of them will not create a cycle in our graph.
So that's why you can take them.
If I am taking it, then I need to add that cost.
And finally I'm returning the cost.
That's very, very simple.
All right.
So that's why I said that Kruskal algorithm is highly recommended.
So whenever you encounter a problem, a problem and you have to option curriculum's always try to go
for the Google algorithm because it is very simple and very fast to implement rate.
So that said, guys.
That is all that I want to discuss in this video, so I will see you in the next one.
Thank you.