Redundant Connection II


  • 0

    Click here to see the full article post


  • 0
    H

    I don't know what does candidates[all(seen)] mean.Could you explain it for me?@awice


  • 0

    @haiyun all(iterable) returns a boolean: true if and only if no item in the iterable is falsy.
    When coerced to int (for use as an index), False becomes 0 and True becomes 1.


  • 0
    H

    @awice Oh,I see!Thanks!When there doesn't exist cycle,there must be two candidate edges which have a common child.That means there are two elements in candidate list. We have to choose either the first one or the last one element from the candidate list.The criteria is whether all nodes could be traversed.If can that means the edges appeared in front could form a tree,delete the last one,or delete the first one.
    Your algorithm explanation is so excellent!I appreciate it!


  • 0
    X

    I am having trouble understanding how the DFS works. Doesn't the order of candidates depend on the order that the edges are listed? How does visiting every node in a DFS help select a candidate? And lastly, I feel like I'm missing something important here, but shouldn't a DFS from the root always visit every node?

    For example, 3->1->4->2->1. The candidates are [2,1] and [3,1] and either can be the first or last candidate depending on which comes first in the input array. A DFS visits every node. The choice should be [2,1] because it is in a cycle. Please help, thank you.


  • 0
    H

    @xpickles The two candidates are the edges that indicate a certain node with two parents. The following codes demonstrate that we save the first parent of the node when it has two parents:
    for u, v in edges:
    if v in parent:
    candidates.append((parent[v], v))
    candidates.append((u, v))
    else:
    parent[v] = u
    When using dfs via children dict(an edge is not in it),it won't traverse all nodes if the first edge of the two candidates is in the cycle.So we should delete the first edge and keep the last one.


  • 0
    X

    @haiyun I see, so the second candidate edge is not stored in the parent dict, so the children dict will be missing an edge. If the missing edge prevents the DFS from visiting every node, then that means the missing edge is necessary and the first candidate edge should be removed instead. Thank you so much!


Log in to reply
 

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