My non-recursive solution missed a node?


  • 0
    G

    Input: {0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}
    Output: {1,2,5#2,3#3,4,4#4,5,5#5}
    Expected: {0,1,5#1,2,5#2,3#3,4,4#4,5,5#5}

    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if node is None:
                return None
            visited = {}
            visited[node] = UndirectedGraphNode(node.label)
            stack = [node]
            while stack != []:
                node = stack.pop()
                for nn in node.neighbors:
                    if nn in visited:
                        visited[node].neighbors.append(visited[nn])
                        continue
                    visited[nn] = UndirectedGraphNode(nn.label)
                    visited[node].neighbors.append(visited[nn])
                    stack.append(nn)
            return visited.values()[0]
    

    But, this solution does basically the same thing. I really can't figure out what is going on.


  • 0
    D

    The problem in your code is this:

    visited is a dictionary, which means the (key, value) pairs stored in it are UNORDERED. So you can't use visited.values()[0] to get the first element. The following code is working. I changed 'node' in the while loop to current and return visited[node] instead.

    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if node is None:
                return None
            visited = {}
            visited[node] = UndirectedGraphNode(node.label)
            stack = [node]
            while stack != []:
                current = stack.pop()
                for nn in current.neighbors:
                    if nn in visited:
                        visited[current].neighbors.append(visited[nn])
                        continue
                    visited[nn] = UndirectedGraphNode(nn.label)
                    visited[current].neighbors.append(visited[nn])
                    stack.append(nn)
            return visited[node]

Log in to reply
 

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