python union find set with path compression

  • 2
    class Solution(object):
        def numIslands2(self, m, n, positions):
            pa = {}
            def get_root(key):
                root = key
                while pa[root] != root:
                    root = pa[root]
                while pa[key] != key:
                    nxt = pa[key]
                    pa[key] = root
                    key = nxt
                return root
            ans = []
            for x, y in positions:
                if (x, y) in pa:
                    neighbors = {get_root(p) for p in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] if p in pa}
                    ans.append(ans[-1] + 1 - len(neighbors))
                    pa[(x, y)] = (x, y)
                    for nx, ny in neighbors:
                        pa[(nx, ny)] = (x, y)
            return ans[1:]

Log in to reply

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