Breadth First Search : Shortest Path using Python

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 ?

#Topic : Graphs
#Url :

def bfs(i, n, E):

	level = [-1] * (n+1)
	queue = []
	level[i] = 0

	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]

	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])

	s = int(input())
	distance = bfs(s, n, E)
	dist = []
	for i in distance[1:]:
		if i > 0:
		if i < 0:

	print(" ".join(dist))

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.


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.


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.


1 Like