Python union find solution


  • 0
    N

    Idea coming from C++/Java, Union Find with explanation, O(n)

    class Solution(object):
    
    def findRedundantDirectedConnection(self, edges):
        if not edges:
            return []
        
        parent = [-1] * (len(edges) + 1)
        candidate_one, candidate_two = [-1, -1], [-1, -1]
        for edge in edges:
            if parent[edge[1]] != -1:
                candidate_one = [parent[edge[1]], edge[1]]
                candidate_two = [edge[0], edge[1]]
            else:
                parent[edge[1]] = edge[0]
        parent = range(len(edges) + 1)
        
        for edge in edges:
            if edge[0] == candidate_two[0] and edge[1] == candidate_two[1]:
                continue
            x, y = edge[0], edge[1]
            x_parent = self.find(parent, x)
            y_parent = self.find(parent, y)
            if x_parent == y_parent:
                if candidate_one[0] == -1:
                    return edge
                return candidate_one
            parent[x_parent] = y_parent 
        return candidate_two
        
    def find(self, parent, x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

Log in to reply
 

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