My non-recursive solution missed a node?

• 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.

• 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]``````

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