# Compact Python.

• Pretty much just Wikipedia's Disjoint-set forests, using "union by rank" and "path compression". I don't see the point of `m` and `n`, so I ignore them.

``````def numIslands2(self, m, n, positions):
parent, rank, count = {}, {}, [0]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x, y = find(x), find(y)
if x != y:
if rank[x] < rank[y]:
x, y = y, x
parent[y] = x
rank[x] += rank[x] == rank[y]
count[0] -= 1
x = parent[x] = i, j
rank[x] = 0
count[0] += 1
for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if y in parent:
union(x, y)
return count[0]
``````

Too bad Python 2 doesn't have `nonlocal` yet, hence the somewhat ugly `count[0]` "hack". Here's a different way:

``````def numIslands2(self, m, n, positions):
parent, rank = {}, {}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x, y = find(x), find(y)
if x == y:
return 0
if rank[x] < rank[y]:
x, y = y, x
parent[y] = x
rank[x] += rank[x] == rank[y]
return 1
counts, count = [], 0
for i, j in positions:
x = parent[x] = i, j
rank[x] = 0
count += 1
for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if y in parent:
count -= union(x, y)
counts.append(count)
return counts``````

• Hi, I tried your first method, without rank, it still AC. I wonder why you have rank here. As far as I know from the wiki, it seems to make it fast. Am I right?

``````def numIslands2(self, m, n, positions):
parent, rank, count = {}, {}, [0]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]

def union(x, y):
x, y = find(x), find(y)
if x != y:
# if rank[x] < rank[y]:
#     x, y = y, x
parent[y] = x
count[0] -= 1
x = parent[x] = i, j
rank[x] = 0
count[0] += 1
for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if y in parent:
union(x, y)
return count[0]
``````

• Yes, it's for speed.

• @StefanPochmann Very similar to yours, perhaps a bit more Object-Oriented. BTW, what is your runtime?

``````
class UnionFind(object):

def __init__(self, n):
self.idxs = [-1] * n
self.rank = [0] * n
self.unions = 0

def find(self, x):
if x == self.idxs[x]: return x
self.idxs[x] = self.find(self.idxs[x])
return self.idxs[x]

def union(self, x, y):
rx = self.find(x)
ry = self.find(y)
if rx != ry:
if self.rank[rx] > self.rank[ry]:
self.idxs[ry] = rx
else:
self.idxs[rx] = ry
if self.rank[ry] == self.rank[rx]:
self.rank[ry] += 1
self.unions +=1

class Solution(object):
def numIslands2(self, m, n, positions):
grid, UF, res = [[[0] * n] * m], UnionFind(m * n), []
for i, (r, c) in enumerate(positions):
UF.idxs[n * r + c] = n * r + c
for d in {(-1,0), (1,0), (0,1), (0,-1)}:
px, py = r + d[0], c + d[1]
if 0 <= px < m and 0 <= py < n and UF.idxs[n * px + py] != -1:
UF.union(n * px + py, n * r + c)
res.append(i + 1 - UF.unions)
return res
# Runtime: 504ms
``````

• Thanks for sharing the solution! But I have a simple maybe stupid question.
Why do you use count = [0]? I try to just use count = 0, but there is this error with 'no defined variable', count. This is my code

``````def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
parent = {}
count = 0
result = []
def find(x):
if parent[x] != x:
return find(parent[x])
else:
return x

def union(x, y):
x, y = find(x), find(y)
if x!=y:
parent[y] = x
count -= 1

for pos in positions:
i, j = pos
pos = (i, j)
parent[pos] = pos
count += 1
for neighbor in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
if neighbor in parent:
union(pos, neighbor)
result.append(count)
return result
``````