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

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

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

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

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