# DFS and Union Find solution in Python

• First solution use DFS. Second solution use Union Find.

``````# Accepted
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
# DFS
if not len(grid):
return 0
maxRow = len(grid)
maxCol = len(grid[0])
visited = [[0 for j in range(maxCol)] for i in range(maxRow)]
dir = [[0,1],[0,-1],[1,0],[-1,0]]   #direction vector，4 different direciton from (x,y)

def dfs(x, y):
if x < 0 or y < 0 or x >= maxRow or y >= maxCol:
return False
if grid[x][y] == '0' or visited[x][y]:
return False
visited[x][y] = 1
for direction in dir:
dfs(x+direction[0], y + direction[1])
return True

count = 0
for i in range(maxRow):
for j in range(maxCol):
if dfs(i,j):
count += 1
return count

# Accepted
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
#Union Find

if not len(grid):
return 0
maxRow = len(grid)
maxCol = len(grid[0])
id = [i for i in range(maxRow * maxCol)]
self.count = sum([grid[i][j] == '1'  for i in range(maxRow) for j in range(maxCol) ])

def find(i):
while i != id[i]:
id[i] = id[id[i]]
i = id[i]
return i

def union(i, j):
iRoot = find(i)
jRoot = find(j)
if iRoot == jRoot:
return
else:
id[iRoot] = jRoot
self.count -= 1

for i in range(maxRow):
for j in range(maxCol):
if grid[i][j] == '0': continue
curNode = i * maxCol + j
if j < maxCol-1 and grid[i][j+1] == '1':
union(curNode, curNode + 1)
if i < maxRow-1 and grid[i+1][j] == '1':
union(curNode, curNode + maxCol)
return self.count``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.