Python solution 52ms

  • 0
    class Solution(object):
        def findRedundantDirectedConnection(self, edges):
            nodes = set()
            parent = collections.defaultdict(list)
            for node, child in edges:
            # 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:
                # 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
                seen = []
                while node not in seen:
                    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.