O(N) Python solution with detailed explanation


  • 0
    L

    The input graph either has loop or no loop, either has a node with dual-parent or no such node. When there is a node with two parents, we can label the two edges to its parents as E1 and E2 following the order of their appearance in the input list. We have 4 cases:

    1, yes loop, yes dual. One of E1 and E2 must be in the loop. Need to remove the one that's in the loop.
    2, no loop, yes dual. Need to remove E2 because it's the latter one.
    3, yes loop, no dual. Need to remove the last edge added to the loop.
    4, no loop, no dual. Impossible.

    Steps in my solution:

    1, go through all edges and save parent(s) for each node in a dictionary. If one node has already got a parent, save the current edge in extra. So E1 is in the dictionary and E2 is in extra.
    2, if there is a node with two parents, start from that node and see if there is a loop in the dictionary. If there is a loop, remove E1. Otherwise remove E2, because either E2 is in a loop in the input graph or the input graph doesn't have a loop.
    3, if there is no such node, there must be a loop in the dictionary. Note that the root node must be in the loop, so start from any node and we will end up in the loop. Find the loop and remove the last edge added into the loop.

    Discussions:

    1, the method works with generalized notation of nodes, i.e. the N nodes doesn't need to be labeled as 1..N.
    2, I don't like how I implemented the 3rd step. Suggestions are welcome!

    class Solution(object):
        def findRedundantDirectedConnection(self, edges):
            """
            :type edges: List[List[int]]
            :rtype: List[int]
            """
            parentOf, edgeInd, extra = {}, {}, []
            for parent, child in edges:
                if child in parentOf:
                    extra = [parent,child]
                else:
                    parentOf[child] = parent
            if extra:
                child = extra[1]
                parent = parentOf[child]
                while parent in parentOf and parent != child:
                    parent = parentOf[parent]
                if parent == child:
                    return [parentOf[child],child]
                return extra
            slow, fast, edgeInd = child, parentOf[parent], {}
            for i, v in enumerate(edges):
                edgeInd[v[1]] = i
            while slow != fast:
                slow = parentOf[slow]
                fast = parentOf[parentOf[fast]]
            loopInd = [edgeInd[slow]]
            while parentOf[slow] != fast:
                slow = parentOf[slow]
                loopInd.append(edgeInd[slow])
            return edges[max(loopInd)]
    

Log in to reply
 

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