**Solution**

**Number of Islands** https://leetcode.com/problems/number-of-islands/

**DFS to find Connected Components: O(V + E)**

- One confusing thing about this question is to understand what is really being asked? All the 1s in the example below make up an island.

11110

11010

11000

00000 - Once you understand what is being asked, the question is a lot simpler. Just run DFS to find connected components.
- During DFS, mark as 0 to indicate visited status. This makes sure that we do not use any additional space.

```
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
try:
M, N = len(grid), len(grid[0])
except:
return 0
num_islands = 0
for i in range(M):
for j in range(N):
if grid[i][j] == "1":
self.dfs(i,j,grid)
num_islands += 1
return num_islands
def dfs(self, i, j, board):
board[i][j] = 0 # Mark as 0 to indicate visited status
for a,b in ((i+1,j), (i-1,j), (i,j+1), (i,j-1)):
if 0<=a<len(board) and 0<=b<len(board[0]) and board[a][b] == "1":
self.dfs(a,b,board)
return
```