Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
disjoint-set-union solution in Speedy category for Radiation Search by 1-more
def checkio(matrix):
N, M = len(matrix), len(matrix[0])
parent, size=[i for i in range(N*M)], [1]*N*M
def find_set(v):
if v != parent[v]: parent[v] = find_set(parent[v])
return parent[v]
def union_sets(a, b):
a, b = find_set(a), find_set (b)
if a != b:
if size[a] < size[b]: a, b = b, a
parent[b] = a
size[a] += size[b]
for i in range(N):
for j in range(M):
if i>0 and matrix[i][j]==matrix[i-1][j]: union_sets(i*N+j, (i-1)*N+j)
if j>0 and matrix[i][j]==matrix[i][j-1]: union_sets(i*N+j, i*N+j-1)
index, value= max(enumerate(size), key=lambda x: x[1])
return [value, matrix[index//N][index%N]]
Oct. 6, 2015
