# Python solution using Tarjan algorithm

• ``````class node:
def __init__(self,val):
self.color=0
self.parent=0
self.rank=0
self.val=val
class Solution:
# @param grid, a list of list of characters
# @return an integer
def makeset(self,u):
u.parent=u
u.rank=0
def find(self,u):
if u.parent==u:
return u
else:
u.parent=self.find(u.parent)
return u.parent
def union(self,x,y):
xRoot=self.find(x)
yRoot=self.find(y)
if xRoot.rank>yRoot.rank:
yRoot.parent=xRoot

elif xRoot.rank<yRoot.rank:
xRoot.parent=yRoot

elif xRoot.val!=yRoot.val:
yRoot.parent=xRoot
xRoot.rank=xRoot.rank+1

def update(self,u,i,j):
if u.color:
return
u.color=1
self.makeset(u)
surrounding=[[i-1,j],[i,j-1],[i,j+1],[i+1,j]]
#surrounding=[[i,j-1],[i-1,j],[i+1,j],[i,j+1]]
flag=0
for t in surrounding:
a=t[0]
b=t[1]
if a<0 or a>=self.m or b<0 or b>=self.n  or self.grid[a][b]=='0':
continue
flag=1
v=self.tree[a][b]
if v.color:
continue
self.update(v,a,b)
self.union(u,v)
if not flag:
self.find(u).parent=u
u.color=2
def numIslands(self, grid):
self.islands=[]
self.m=len(grid)
if not self.m:
return 0
self.grid=grid
self.n=len(grid[0])
self.tree=[[node(self.m*i+j) for j in range(self.n)] for i in range(self.m)]
for i in range(self.m):
for j in range(self.n):
u=self.tree[i][j]
if grid[i][j]=='0':
continue
self.update(u,i,j)
if self.find(u).parent.val not in self.islands:
self.islands.append(u.parent.val)
return len(self.islands)``````

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