I came across the problem **Breadth First Search: Shortest Reach** in Hackerrank and here was my solution in **python**. However my code only passed one Test Cases among the 7. Where am I wrong in this implementation ?

```
#Hackerrank
#Topic : Graphs
#Url : https://www.hackerrank.com/challenges/bfsshortreach/problem
def bfs(i, n, E):
level = [-1] * (n+1)
queue = []
level[i] = 0
queue.append(i)
while len(queue) > 0:
head = queue[0]
queue = queue[1:]
for j,k in E:
if j == head:
if level[k] == -1:
level[k] = 1 + level[j]
queue.append(k)
return level
q = int(input())
for case in range(q):
e = input().split(" ")
n = int(e[0])
m = int(e[1])
E = []
for edge in range(m):
e = input().split(" ")
u = int(e[0])
v = int(e[1])
E.append([u,v])
s = int(input())
distance = bfs(s, n, E)
dist = []
for i in distance[1:]:
if i > 0:
dist.append(str(i*6))
if i < 0:
dist.append(str(-1))
print(" ".join(dist))
#print("")
```

It is an â€śundirectedâ€ť graph.

E.append([u,v]) is cool.

You have missed E.append([v,u]).

Add that andâ€¦ youâ€™ll get a better result and more test cases will pass.

But, donâ€™t celebrate just yet! Youâ€™ll get a TLE for some test cases.

The reason being, your BFS logic implementation involves scanning through the edge list repeatedly till I find all the neighbours of the node.

Say your edge list looks like this => [1,2], [3,4], â€¦all unwanted pairsâ€¦[1,5]

For node 1, you are looking through the entire list till you find [1,5]. YOU SHOULD DO BETTER.

Maintain a graph as an adjacency list instead.

i.e.

1 => 2,5â€¦ (all neighbours of 1)

2 => all neighbours of 2

and so onâ€¦

Hereâ€™s how I would implement in Pythonâ€“

Hope your issue is resolved now.

Peace.

Actually I figured out the adjacency list part beforeâ€¦but I was getting Wrong Answer and not TLE, so I ignored that part. Anyway thanks for the help !

Yeahâ€¦it worked except that one Test Case gave TLE. I guess I will be able to fix that. Thank you for the help.

Peace.

1 Like