Python Union-find with short-circuit beats 100%


  • 0
    D
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        d={}
        
        def find(node):
            c=node
            # trace up to find the root
            while d[node]!=node:
                node=d[node]
            # short-circuit the connection
            d[c]=node
            return node
            
        for e in edges:
            a=e[0]
            b=e[1]
            if a>b:
                a,b=b,a
            # now a<b in this connection
            if a in d and b in d:
                if find(a)==find(b): # they are already connected, return this edge
                    return e
                else: # they are not connected, point one root to the other
                    d[b]=d[a]
            else:
                if a not in d and b not in d: # both are new
                    d[a]=a
                    d[b]=a
                if a not in d: # only a is new, point a to the root of b
                    d[a]=find(b)
                if b not in d: # only b is new, point b to the root of a
                    d[b]=find(a)
            #print d
        return []

Log in to reply
 

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