Python Union and Find solution (without DFS or BFS)

• ``````class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0
m=len(grid)
n=len(grid[0])
djset=[[0 for j in range(n+1)]for i in range(m+1)]
id=1
for i in range(m):
for j in range(n):
if grid[i][j]=='1':
djset[i+1][j+1]=id
id+=1

operation=self.getCommand(djset,m,n)

union=[-1 for i in range(id)]
for a,b in operation:
classA=self.find(union,a)
classB=self.find(union,a=b)
if classA==classB:
continue
self.union(union,classA,classB)

return self.countIsland(union)

def countIsland(self,union):
count=0
for h in union[1:]:
if h<0:
count+=1
return count
def union(self,union,classA,classB):
if union[classA]<=union[classB]:
union[classA]+=union[classB]
union[classB]=classA
else:
union[classB]+=union[classA]
union[classA]=classB

def find(self,union,a):
id=a
x=union[id]
while x>0:
id=x
x=union[id]
return id

def getCommand(self,djset,m,n):
operation=[]
for i in range(1,m+1):
for j in range(1,n+1):
if djset[i][j]>0:
if djset[i-1][j]>0:
operation.append((djset[i][j],djset[i-1][j]))
if djset[i][j-1]>0:
operation.append((djset[i][j],djset[i][j-1]))
return operation``````

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