1 00:00:01,050 --> 00:00:03,120 Hi, everyone, welcome to this new video. 2 00:00:03,150 --> 00:00:07,040 So in this video, we are going to discuss about discussion number of islands. 3 00:00:07,530 --> 00:00:12,190 So in this question we are provided with right to degrade and destroy, degrade will have 110 rules. 4 00:00:12,510 --> 00:00:16,260 So when represent land and a zero percent water. 5 00:00:16,379 --> 00:00:18,890 And we need to find out the total number of islands. 6 00:00:20,130 --> 00:00:21,980 So let us try to take one example. 7 00:00:21,990 --> 00:00:27,360 Let us try to understand the problem statement, given this to the array of zeros and ones. 8 00:00:27,900 --> 00:00:29,070 So the number of islands. 9 00:00:29,100 --> 00:00:31,260 So in this case, the output is one. 10 00:00:32,040 --> 00:00:32,850 Why this one? 11 00:00:32,850 --> 00:00:34,920 Because you can see this is one island. 12 00:00:40,030 --> 00:00:48,860 Right, so we have one island here, so that's where the output for this is when we need to return around 13 00:00:48,860 --> 00:00:50,700 to the total number of islands. 14 00:00:50,950 --> 00:00:52,110 So we have one island. 15 00:00:52,420 --> 00:00:52,810 Right. 16 00:00:53,170 --> 00:00:54,670 Let's take one more example. 17 00:00:57,890 --> 00:01:07,340 So in this second example, let's try to find out the total number of islands here, so I think if I 18 00:01:07,340 --> 00:01:09,500 start from this, this is one collection. 19 00:01:10,960 --> 00:01:12,410 This is you one island. 20 00:01:13,340 --> 00:01:15,080 This is another island. 21 00:01:15,080 --> 00:01:17,290 An island is basically surrounded by water. 22 00:01:18,170 --> 00:01:20,720 And this is your third island. 23 00:01:23,150 --> 00:01:29,720 So here we have three islands, so that's why the output is three late, so I hope you have understood 24 00:01:29,720 --> 00:01:30,250 the question. 25 00:01:30,590 --> 00:01:33,310 Now the question is how we can solve this problem. 26 00:01:35,920 --> 00:01:39,780 So let's see how we can solve this problem. 27 00:01:41,940 --> 00:01:47,160 So this is basically your standard DFS problem. 28 00:01:47,760 --> 00:01:52,850 So this is nothing, but you just need to find out the number of connected components in the graph, 29 00:01:54,360 --> 00:01:58,230 number of connected components in a graph. 30 00:01:59,640 --> 00:02:00,740 This is that problem. 31 00:02:00,930 --> 00:02:08,229 So the number of violent problem is just the variation of finding out the number of connected components. 32 00:02:08,580 --> 00:02:13,870 So given a graph, this is one graph and we need to find out a number of connected components. 33 00:02:14,100 --> 00:02:17,130 So in this graph, I have only one connected component. 34 00:02:19,370 --> 00:02:21,760 And in the below example, I have three connected. 35 00:02:22,490 --> 00:02:24,680 So that's why the output was three and four. 36 00:02:24,710 --> 00:02:30,350 Finding out the number of connected component, we can use defense in depth first, such that we have 37 00:02:30,350 --> 00:02:34,330 discussed in our previous videos to how the offense will work here. 38 00:02:34,790 --> 00:02:36,640 Let's take below example. 39 00:02:37,280 --> 00:02:42,720 So what I'm going to do is let's talk about this example. 40 00:02:44,030 --> 00:02:46,490 So this is our graph. 41 00:02:47,220 --> 00:02:50,990 What I will do, I will start BFX from the first element. 42 00:02:51,290 --> 00:02:54,020 So I start the offense from this element, element one. 43 00:02:54,380 --> 00:03:00,500 And if I start the offense from one element, so from a given index, I can move in eight directions. 44 00:03:00,770 --> 00:03:01,220 Right. 45 00:03:01,730 --> 00:03:03,980 I can move in either directions. 46 00:03:05,220 --> 00:03:07,460 So what I'm going to do is I will move here. 47 00:03:07,490 --> 00:03:10,240 I will cover this in DFS again, DFS. 48 00:03:10,250 --> 00:03:12,830 So when the offense will cover all these elements. 49 00:03:13,880 --> 00:03:14,260 Right. 50 00:03:14,570 --> 00:03:19,310 So how do you find out the number of concrete components, the number of connected components can be 51 00:03:19,310 --> 00:03:22,100 calculated, how many times you are running or DFS? 52 00:03:22,120 --> 00:03:26,960 A lot of them, the number of times your defense algorithm will run, that will be the number of connected 53 00:03:26,960 --> 00:03:27,490 component. 54 00:03:27,800 --> 00:03:28,180 Right. 55 00:03:28,190 --> 00:03:29,330 And that will be your answer. 56 00:03:29,570 --> 00:03:34,370 So if I render DFS from this element, DFS will visit all these four elements. 57 00:03:35,210 --> 00:03:41,570 Now, if you go to this element, element one, then you will not start DFS again because you have visited 58 00:03:41,570 --> 00:03:42,190 this element. 59 00:03:42,470 --> 00:03:44,930 So that means we need to take one visitor. 60 00:03:44,930 --> 00:03:51,710 That is also, if it's right in the center DFS algorithm used to have visited that, then I will come 61 00:03:51,710 --> 00:03:51,890 here. 62 00:03:52,580 --> 00:03:53,660 So this is element zero. 63 00:03:53,930 --> 00:03:56,630 We will not start DFS from here, 11 zero. 64 00:03:56,630 --> 00:03:59,150 Do not start DFS from here, 11 zero. 65 00:03:59,150 --> 00:04:00,620 Do not start DFS from here. 66 00:04:00,770 --> 00:04:02,420 Element one already visited. 67 00:04:03,020 --> 00:04:04,640 Element one already visited. 68 00:04:04,640 --> 00:04:06,800 Element zero nor DFS. 69 00:04:07,430 --> 00:04:08,720 Do not start DFS. 70 00:04:08,720 --> 00:04:09,890 Do not start DFS. 71 00:04:10,220 --> 00:04:11,480 Do not start DFS. 72 00:04:11,750 --> 00:04:12,860 Do not start DFS. 73 00:04:12,860 --> 00:04:14,080 Oh this is Elementalist. 74 00:04:15,170 --> 00:04:21,709 Since this is element one, I will start DFS from here and DFS will be able to find out only one land. 75 00:04:22,280 --> 00:04:22,700 Right. 76 00:04:22,880 --> 00:04:25,490 So this is no visited next. 77 00:04:25,490 --> 00:04:29,570 Do not start DFS from here, do not start DFS from here. 78 00:04:29,930 --> 00:04:33,560 Do not start DFS, do not start DFS, do not start DFS. 79 00:04:33,770 --> 00:04:39,260 Now we will start DFS from here because this is not visited and this is when if I will start DFS and 80 00:04:39,260 --> 00:04:41,290 DFS can move in either directions. 81 00:04:42,450 --> 00:04:48,450 So I am going to visit this one element also now if I will come here. 82 00:04:48,750 --> 00:04:51,070 So this is already visited, right? 83 00:04:51,090 --> 00:04:52,560 This is already visited. 84 00:04:52,570 --> 00:04:53,770 So they will not visit again. 85 00:04:54,090 --> 00:04:56,430 So how many times we run the algorithm? 86 00:04:56,670 --> 00:05:04,710 We run the algorithm three times one time, the second time and third time since we are under the official 87 00:05:04,710 --> 00:05:05,650 Werdum three times. 88 00:05:06,000 --> 00:05:07,950 So there are three connected component. 89 00:05:07,980 --> 00:05:10,530 That is, there are three number of aliens. 90 00:05:11,340 --> 00:05:14,120 So that's how you can use DFS algorithm here. 91 00:05:15,360 --> 00:05:17,760 And let's talk about about one example. 92 00:05:18,090 --> 00:05:23,490 So in this above example, what you are going to do is you are standing at this. 93 00:05:24,060 --> 00:05:28,590 You will start the office since the office can move in all the introductions. 94 00:05:28,950 --> 00:05:38,190 So you are going to visit everyone that is present now from this one large DFS because already visited, 95 00:05:38,190 --> 00:05:38,940 already visited. 96 00:05:38,940 --> 00:05:40,250 Already visited, already visited. 97 00:05:40,350 --> 00:05:40,990 This is zero. 98 00:05:41,280 --> 00:05:43,590 So the majority of it's already visited. 99 00:05:43,590 --> 00:05:44,760 Visited this is zero. 100 00:05:44,760 --> 00:05:46,590 Do not start already visited zero. 101 00:05:46,590 --> 00:05:49,680 Do not start already visited already visitor zero. 102 00:05:49,680 --> 00:05:52,140 Do not start the first DFS. 103 00:05:52,140 --> 00:05:53,280 Do not start DFS. 104 00:05:53,280 --> 00:05:54,180 No, no. 105 00:05:54,590 --> 00:05:55,910 Naughty, naughty, naughty. 106 00:05:55,920 --> 00:06:01,110 If it's so in this example we are running the DFS algorithm only one time. 107 00:06:01,890 --> 00:06:05,910 So that's why the output is one and one is the number of connected components. 108 00:06:06,720 --> 00:06:09,360 So I hope you have understood the given problem. 109 00:06:09,690 --> 00:06:15,300 So again, what do you need to write the code for finding out the number of connected components? 110 00:06:18,090 --> 00:06:18,840 Ethnographies. 111 00:06:19,880 --> 00:06:25,580 And we have done similar problem in our previous videos also, so you can refer the code from there 112 00:06:26,450 --> 00:06:29,570 right in next video, we will be writing the code for this problem. 113 00:06:29,570 --> 00:06:34,350 But I highly recommend that you try calling this problem yourself before watching the solution video. 114 00:06:36,260 --> 00:06:38,480 So this isn't about this video, guys. 115 00:06:38,480 --> 00:06:39,900 I will see you in the next one. 116 00:06:40,220 --> 00:06:40,760 Thank you.