# Breadth first search problem 154

Back to General discussions forum

Franz_Nilsson     2016-06-06 07:43:10

Hallo!

Im having a bit trouble with problem 145. My program gives the correct answer when I try the example, but when I submit for the larger data set I get a completly different answer!

My output:

-1 0 0 0 0 0 8 8 8 8 8 12 12 12 12 18 18 18 18 28 35 35 35 20 27 27 31 31 31 32 41 41 41 41 6 16 16 16 29 9 17 26 39 39 48 3 24 37 15

-1 48 37 35 35 31 12 41 0 18 6 3 0 29 17 41 12 18 0 26 8 15 20 41 35 16 18 8 0 12 39 8 8 27 12 0 9 31 24 18 31 8 16 16 39 27 41 32 28

As you can see, they are completly different! But I dont understand what I've done wrong. The given answer seems strange to, since the search should start at node 0 but seems to start at node 48?

My code is as follows:

class Node(object):

``````def __init__(self,idnr):

self.ID=idnr
self.next=[]
self.state=False

i=0

while i<len(self.next) and int(self.next[i].ID)<int(neighboor.ID):
i+=1
if i==len(self.next):
self.next.append(neighboor)
else:
self.next=self.next[0:i]+[neighboor]+self.next[i:]

def seen(self):

self.state=True

def __str__(self):

ret='Node '+str(self.ID)+'---> '
ret+=' '.join(str(i.ID) for i in self.next)
return ret
``````

if name=='main':

``````#N: Amount of nodes
#M: Amount of edges

N,M=raw_input().split()

nodes=dict()

for i in range(0,int(M)):

#Get all the edges

n1 , n2 = raw_input().split()

if n1 not in nodes.keys():

nodes[n1]=Node(n1)

if n2 not in nodes.keys():

nodes[n2]=Node(n2)

q=[]    #Create a FIFO que:

#Step 1:

nodes['0'].seen()

q.append(nodes['0'])

while len(q)>0:

#Step 2:

curr=q.pop(0)

for nxt in curr.next:

#Step 3:

if not nxt.state:

#Step 4:

nxt.seen()
q.append(nxt)

print ' '.join( i for i in answer )
``````

Any help is appreciated!

Best regards // Franz. N

Hi Franz. I had a similar problem to you so I hope I can be helpful and explain how I resolved it. I think the issue comes with this bit of code :

if not nxt.state:

``````        #Step 4:

nxt.seen()
q.append(nxt)
``````

The problem here is your adding the curr.id to the answer as you "see" the node which is what i did. What the question actually wants you is to for the answer id's to be in order of the node ids.

for example. the first number in the answer should be the ID of the node that lead to node 0 being seen. In this special case we use -1 the second number should be the ID of the node that lead to the node with ID of 1 being seen. so in terms of your answers: Node1 was first discovered when node 48 was the current. not when node 0 was the current which is what you put. In short youve ordered your answer in terms of when nodes are "seen" during the code NOT in order of the increasing NODE IDS. Hope i've been useful, if not ill try again. Good Luck!

Franz_Nilsson     2016-06-17 21:28:46