# Python Union-Find solution without using Set

• Use "root point" instead of set to record an area of connected land. Every point can trace its "root" by looking up a chained dictionary, which works like a linked list.

``````def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""

chainmap = {}

def getNeighbors(i, j):
return [(ii, jj) for (ii, jj) in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)) \
if (ii, jj) in chainmap]

def getRoot(point):
p = point
while chainmap[p] != p:
p = chainmap[p]
chainmap[point] = p # memorize for future fast trace
return p

ret = []
nroots = 0
for (i, j) in positions:
hasRoot = False
rootToMerge = []
for neighbor in getNeighbors(i, j):
root = getRoot(neighbor)
if not hasRoot:
chainmap[(i, j)] = root
hasRoot = True
else:
newroot = chainmap[(i, j)]
if root not in rootToMerge and root != newroot:
rootToMerge.append(root)
chainmap[root] = newroot
nroots -= 1
if (i, j) not in chainmap:
chainmap[(i, j)] = (i, j)
nroots += 1
ret.append(nroots)

return ret``````

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