Python solution 52ms


  • 0
    A
    class Solution(object):
        def findRedundantDirectedConnection(self, edges):
    
            nodes = set()
            parent = collections.defaultdict(list)
            for node, child in edges:
                nodes.add(node)
                nodes.add(child)
                parent[child].append(node)
            
            # there is a root node, means some node has 2 parents
            if nodes - set(parent.keys()):
                for child, parents in parent.items():
                    if len(parents) == 2:
                        break
                # there is no circle, break edge to second parent
                res = [parents[1], child]
                for p in parents:
                    node = p
                    while parent[node] and node != child:
                        node = parent[node][0]
                    # there is circle, break edge that creates cirle
                    if node == child:
                        res = [p, child]
                return res
            
            # ther is no root node, break circle to create one
            else:
                seen = []
                while node not in seen:
                    seen.append(node)
                    node = parent[node][0]
    
                circle = set(seen[seen.index(node):])
                for a, b in reversed(edges):
                    if a in circle and b in circle:
                        return [a, b]
                    
            ```

Log in to reply
 

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