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.

