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:
                    ans.append(ans[-1])
                else:
                    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.