Hi, everyone, welcome to this new video.
So in this video, we are going to solve this question, Commutable Island.
So what is the problem statement?
So we are given islands or let's name it.
And so we are provided with an island, right?
We have an island and there are bridges which connect these islands.
And each bridge will have some cost associated with this.
So each bridge has some cost like, say, X, this bridge has a cost of Y and so on.
And what we need to do, we need to find out the bridges with the minimal cost such that all the islands
are connected.
So we need to connect all islands and we need to find out the minimum cost for doing that.
Let's take an example to understand this problem a little more so if we see this example.
So here we can see we have four islands, right, so we have Island one, we have Island Two, we have
Island three and we have Island four.
And this is the edges, right.
B means advisory.
So this is the source.
This is the destination.
And this is debate.
So because I mean one vortex, this is one vertex and either vortex and this is deviate between them.
So the minimum cost is six and the bridges that we are choosing is one, two and one.
So connect one and two.
And what is the cost.
Cost is one.
Right.
So connect one end to end of this one.
Next is connect one end for next one and four.
And the cost is three.
So this one, the cost is three.
Next disconnect for entry, connect for entry and the cost is two.
So this one for entry and the cost is too high.
So this is it.
All the nodes are connected.
All islands are connected now.
And what is the cost?
One plus three four four plus two six.
That's why the output is six.
Right.
So given this advisory, so in the first one is this second on this destination and the third value
is basically right.
So these are indexes 012.
So third on this debate, the cost.
Let's take one more example and let's see so here in this example.
So we have four islands here.
So this is island, one island to Ireland three and Island four.
And we want to connect them such that the cost is minimum.
So it is saying connect one and two with the cost, one to connect one and two, let's connect one and
two.
And the cost is one, two and three.
And the cost is two.
So this one connected to.
And three.
And the cost is to next disconnect one and four with the cost to connect to one and four Vitacost three,
so this one late.
So now all the islands are connected and is the cost three plus two five five plus one six.
So that is the output.
Right.
So that is we need to do here.
We need to find out the minimum cost and we need to make sure that all the islands are connected.
So basically, this is nothing but minimum spanning three.
Right.
So in this problem, it's a very straightforward problem.
We just need to find out the minimum spending tree.
If we are able to find out more and spending three, then what we need to do.
We need to just add these values and that's it.
And that's it.
Right.
So for Finding Nemo, spending, spending, we know two algorithms.
One is critical and another one is primps to what we can do.
We can either implement an algorithm for solving this problem or we can implement Prem's algorithm for
solving this problem.
Right.
So I highly recommend that you try implementing one of them so you can implement primps or you can implement
critical.
So in next video, I will be writing the code for this problem.
But what you should do, you should either implement classical or bems, right?
So this is it, guys.
This is all about this video and next video.
We will be writing the code for this problem.
So I will see you there.
Thank you.
Bye bye.