Python solution using Tarjan algorithm


  • 0
    R
    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)

Log in to reply
 

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