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.

