What does test case {0,1,5#1,2,5#2,3#3,4,4#4,5,5#5} means?


  • 2
    P

    My code failed at test case: {0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}

    If I understand correctly:

    1. node 0 has 1 and 5 as its neighbors
    2. node 1 has 2 and 5 as its neighbors
    3. node 2 has 3 as its neighbors
    4. node 3 has 4 as its neighbors
    5. node 4 has 5 as its neighbors

    I don't understand #4 and #5, why is it described as 3,4,4 and 4,5,5 rather than 3,4 and 4,5 ?


  • 0
    P

    I just figured it out, there can be more than one edges between two nodes. So 3,4,4 means there are two edges between node 3 and node 4.

    My python code got accepted after adding two lines to avoid duplicates in the stack:

            while len(st)>0 and st[-1].label==cur.label:
                st.pop()
    

    The complete code:

    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            
            if node is None:
                return None
            
            # DFS
            st = []   # keep a stack to record our trace progress on the origin graph
            st.append(node)  # start with head
            visited = []  # record the label of node which we have visited already
            copyMap = {}   # a cache for the copied node we are adding during DFS
    
            new_node = UndirectedGraphNode(node.label) 
            copyMap[node.label] = new_node
            new_cur = new_node
    
            while len(st)>0:
    
                cur = st.pop()
                new_cur = copyMap[cur.label]
                while len(st)>0 and st[-1].label==cur.label: # skip duplicates in the stack
                    st.pop()
    
                visited.append(cur.label)
                for nod in cur.neighbors: 
    
                    if nod.label in copyMap:  # the new node we have already created previously
                            new_cur.neighbors.append(copyMap[nod.label])
                    else:  # new node doesn't exist yet, we need to create a new one and save in the map
                            new_n = UndirectedGraphNode(nod.label)
                            copyMap[nod.label] = new_n
                            new_cur.neighbors.append(new_n)
    
                    if not nod.label in visited: 
                            st.append(nod)
                            
            return new_node   
    

  • 0
    H

    "So 3,4,4 means there are two nodes between node 3 and node 4."
    I think you mean "there are two edges between node3 and node4"
    in fact ,it make sense that allow more than one edge between nodes.
    if each edge was tag with a value then it can be understood much easier


Log in to reply
 

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