```
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0
m, n, count = len(grid), len(grid[0]), 0
roots = [-1 for i in xrange(m*n)]
pos = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in xrange(m):
for j in xrange(n):
if grid[i][j] == '1':
count += 1
root = i*n+j
roots[root] = root
for p in pos:
x = i + p[0]
y = j + p[1]
neighbor = x*n + y
if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '0' or roots[neighbor] == -1:
continue
neighborRoot = self.findRoot(roots, neighbor)
if neighborRoot != root:
roots[root] = neighborRoot
root = neighborRoot
count -= 1
return count
def findRoot(self, roots, root):
while roots[root] != root:
roots[root] = roots[roots[root]]
root = roots[root]
return root
```