1 00:00:01,050 --> 00:00:03,180 Hi, everyone, welcome to this new video. 2 00:00:03,210 --> 00:00:07,490 So in this video, we are going to solve this question, Commutable Island. 3 00:00:08,940 --> 00:00:10,400 So what is the problem statement? 4 00:00:10,620 --> 00:00:13,800 So we are given islands or let's name it. 5 00:00:13,800 --> 00:00:19,550 And so we are provided with an island, right? 6 00:00:19,620 --> 00:00:23,520 We have an island and there are bridges which connect these islands. 7 00:00:24,030 --> 00:00:27,440 And each bridge will have some cost associated with this. 8 00:00:27,690 --> 00:00:33,510 So each bridge has some cost like, say, X, this bridge has a cost of Y and so on. 9 00:00:34,020 --> 00:00:41,520 And what we need to do, we need to find out the bridges with the minimal cost such that all the islands 10 00:00:41,520 --> 00:00:42,360 are connected. 11 00:00:42,660 --> 00:00:49,420 So we need to connect all islands and we need to find out the minimum cost for doing that. 12 00:00:50,340 --> 00:00:56,790 Let's take an example to understand this problem a little more so if we see this example. 13 00:00:59,460 --> 00:01:09,000 So here we can see we have four islands, right, so we have Island one, we have Island Two, we have 14 00:01:09,000 --> 00:01:11,250 Island three and we have Island four. 15 00:01:12,690 --> 00:01:14,940 And this is the edges, right. 16 00:01:14,940 --> 00:01:16,580 B means advisory. 17 00:01:17,490 --> 00:01:18,670 So this is the source. 18 00:01:18,840 --> 00:01:20,040 This is the destination. 19 00:01:20,040 --> 00:01:21,060 And this is debate. 20 00:01:21,420 --> 00:01:27,390 So because I mean one vortex, this is one vertex and either vortex and this is deviate between them. 21 00:01:27,690 --> 00:01:32,940 So the minimum cost is six and the bridges that we are choosing is one, two and one. 22 00:01:33,150 --> 00:01:34,320 So connect one and two. 23 00:01:35,340 --> 00:01:36,630 And what is the cost. 24 00:01:37,050 --> 00:01:38,430 Cost is one. 25 00:01:39,270 --> 00:01:39,650 Right. 26 00:01:39,960 --> 00:01:42,250 So connect one end to end of this one. 27 00:01:42,540 --> 00:01:46,650 Next is connect one end for next one and four. 28 00:01:46,740 --> 00:01:48,030 And the cost is three. 29 00:01:48,060 --> 00:01:51,100 So this one, the cost is three. 30 00:01:51,990 --> 00:01:57,000 Next disconnect for entry, connect for entry and the cost is two. 31 00:01:57,330 --> 00:02:01,610 So this one for entry and the cost is too high. 32 00:02:01,920 --> 00:02:02,940 So this is it. 33 00:02:02,940 --> 00:02:04,440 All the nodes are connected. 34 00:02:04,440 --> 00:02:07,190 All islands are connected now. 35 00:02:07,200 --> 00:02:08,280 And what is the cost? 36 00:02:08,310 --> 00:02:10,889 One plus three four four plus two six. 37 00:02:11,160 --> 00:02:12,960 That's why the output is six. 38 00:02:14,310 --> 00:02:14,690 Right. 39 00:02:15,300 --> 00:02:21,810 So given this advisory, so in the first one is this second on this destination and the third value 40 00:02:21,810 --> 00:02:23,330 is basically right. 41 00:02:23,580 --> 00:02:25,240 So these are indexes 012. 42 00:02:25,770 --> 00:02:27,600 So third on this debate, the cost. 43 00:02:28,770 --> 00:02:35,400 Let's take one more example and let's see so here in this example. 44 00:02:35,410 --> 00:02:37,180 So we have four islands here. 45 00:02:37,410 --> 00:02:42,860 So this is island, one island to Ireland three and Island four. 46 00:02:43,140 --> 00:02:46,780 And we want to connect them such that the cost is minimum. 47 00:02:47,190 --> 00:02:53,730 So it is saying connect one and two with the cost, one to connect one and two, let's connect one and 48 00:02:53,730 --> 00:02:54,020 two. 49 00:02:54,360 --> 00:02:58,290 And the cost is one, two and three. 50 00:02:58,290 --> 00:02:59,240 And the cost is two. 51 00:02:59,280 --> 00:03:01,000 So this one connected to. 52 00:03:01,080 --> 00:03:01,470 And three. 53 00:03:02,580 --> 00:03:11,240 And the cost is to next disconnect one and four with the cost to connect to one and four Vitacost three, 54 00:03:12,780 --> 00:03:14,790 so this one late. 55 00:03:15,000 --> 00:03:20,750 So now all the islands are connected and is the cost three plus two five five plus one six. 56 00:03:21,060 --> 00:03:22,470 So that is the output. 57 00:03:23,250 --> 00:03:23,580 Right. 58 00:03:24,060 --> 00:03:25,800 So that is we need to do here. 59 00:03:25,800 --> 00:03:31,980 We need to find out the minimum cost and we need to make sure that all the islands are connected. 60 00:03:32,910 --> 00:03:36,720 So basically, this is nothing but minimum spanning three. 61 00:03:37,530 --> 00:03:37,880 Right. 62 00:03:38,210 --> 00:03:40,980 So in this problem, it's a very straightforward problem. 63 00:03:40,980 --> 00:03:43,340 We just need to find out the minimum spending tree. 64 00:03:43,860 --> 00:03:47,280 If we are able to find out more and spending three, then what we need to do. 65 00:03:47,280 --> 00:03:49,920 We need to just add these values and that's it. 66 00:03:50,700 --> 00:03:51,460 And that's it. 67 00:03:51,480 --> 00:03:51,880 Right. 68 00:03:52,080 --> 00:03:55,320 So for Finding Nemo, spending, spending, we know two algorithms. 69 00:03:55,320 --> 00:03:58,890 One is critical and another one is primps to what we can do. 70 00:03:58,900 --> 00:04:04,380 We can either implement an algorithm for solving this problem or we can implement Prem's algorithm for 71 00:04:04,380 --> 00:04:05,390 solving this problem. 72 00:04:05,970 --> 00:04:06,320 Right. 73 00:04:06,660 --> 00:04:14,790 So I highly recommend that you try implementing one of them so you can implement primps or you can implement 74 00:04:14,790 --> 00:04:15,300 critical. 75 00:04:15,720 --> 00:04:18,810 So in next video, I will be writing the code for this problem. 76 00:04:19,140 --> 00:04:23,690 But what you should do, you should either implement classical or bems, right? 77 00:04:24,030 --> 00:04:25,410 So this is it, guys. 78 00:04:25,410 --> 00:04:28,740 This is all about this video and next video. 79 00:04:29,220 --> 00:04:31,080 We will be writing the code for this problem. 80 00:04:32,130 --> 00:04:33,390 So I will see you there. 81 00:04:34,050 --> 00:04:34,660 Thank you. 82 00:04:34,830 --> 00:04:35,370 Bye bye.