Hi, everyone, welcome to this new video.
So in this video, we are going to discuss about discussion number of islands.
So in this question we are provided with right to degrade and destroy, degrade will have 110 rules.
So when represent land and a zero percent water.
And we need to find out the total number of islands.
So let us try to take one example.
Let us try to understand the problem statement, given this to the array of zeros and ones.
So the number of islands.
So in this case, the output is one.
Why this one?
Because you can see this is one island.
Right, so we have one island here, so that's where the output for this is when we need to return around
to the total number of islands.
So we have one island.
Right.
Let's take one more example.
So in this second example, let's try to find out the total number of islands here, so I think if I
start from this, this is one collection.
This is you one island.
This is another island.
An island is basically surrounded by water.
And this is your third island.
So here we have three islands, so that's why the output is three late, so I hope you have understood
the question.
Now the question is how we can solve this problem.
So let's see how we can solve this problem.
So this is basically your standard DFS problem.
So this is nothing, but you just need to find out the number of connected components in the graph,
number of connected components in a graph.
This is that problem.
So the number of violent problem is just the variation of finding out the number of connected components.
So given a graph, this is one graph and we need to find out a number of connected components.
So in this graph, I have only one connected component.
And in the below example, I have three connected.
So that's why the output was three and four.
Finding out the number of connected component, we can use defense in depth first, such that we have
discussed in our previous videos to how the offense will work here.
Let's take below example.
So what I'm going to do is let's talk about this example.
So this is our graph.
What I will do, I will start BFX from the first element.
So I start the offense from this element, element one.
And if I start the offense from one element, so from a given index, I can move in eight directions.
Right.
I can move in either directions.
So what I'm going to do is I will move here.
I will cover this in DFS again, DFS.
So when the offense will cover all these elements.
Right.
So how do you find out the number of concrete components, the number of connected components can be
calculated, how many times you are running or DFS?
A lot of them, the number of times your defense algorithm will run, that will be the number of connected
component.
Right.
And that will be your answer.
So if I render DFS from this element, DFS will visit all these four elements.
Now, if you go to this element, element one, then you will not start DFS again because you have visited
this element.
So that means we need to take one visitor.
That is also, if it's right in the center DFS algorithm used to have visited that, then I will come
here.
So this is element zero.
We will not start DFS from here, 11 zero.
Do not start DFS from here, 11 zero.
Do not start DFS from here.
Element one already visited.
Element zero nor DFS.
Do not start DFS.
Oh this is Elementalist.
Since this is element one, I will start DFS from here and DFS will be able to find out only one land.
Right.
So this is no visited next.
Do not start DFS from here, do not start DFS from here.
Do not start DFS, do not start DFS, do not start DFS.
Now we will start DFS from here because this is not visited and this is when if I will start DFS and
DFS can move in either directions.
So I am going to visit this one element also now if I will come here.
So this is already visited, right?
This is already visited.
So they will not visit again.
So how many times we run the algorithm?
We run the algorithm three times one time, the second time and third time since we are under the official
Werdum three times.
So there are three connected component.
That is, there are three number of aliens.
So that's how you can use DFS algorithm here.
And let's talk about about one example.
So in this above example, what you are going to do is you are standing at this.
You will start the office since the office can move in all the introductions.
So you are going to visit everyone that is present now from this one large DFS because already visited,
already visited.
Already visited, already visited.
This is zero.
So the majority of it's already visited.
Visited this is zero.
Do not start already visited zero.
Do not start already visited already visitor zero.
Do not start the first DFS.
Do not start DFS.
No, no.
Naughty, naughty, naughty.
If it's so in this example we are running the DFS algorithm only one time.
So that's why the output is one and one is the number of connected components.
So I hope you have understood the given problem.
So again, what do you need to write the code for finding out the number of connected components?
Ethnographies.
And we have done similar problem in our previous videos also, so you can refer the code from there
right in next video, we will be writing the code for this problem.
But I highly recommend that you try calling this problem yourself before watching the solution video.
So this isn't about this video, guys.
I will see you in the next one.
Thank you.