Roads and Libraries using Python

algorithms
bfs
data-structure
graph-theory
graphs
hackerrank
python
python3

#1

I came across the Roads and Libraries problem in Hackerrank and here is my solution in python. I am using adjacency list to represent the graph, yet most of the Test Cases failed due to Timeout. How can I
improve the efficiency of my code ?

def bfs(i, n, E, level):

	#level = [-1] * (n+1)
	queue = []
	level* = 0
	queue.append(i)
	vertices = 1
	
	#print(E)
	while len(queue) > 0:
		head = queue[0]
		queue = queue[1:]
		for k in E[head]:
			if level[k] == -1:
				level[k] = 1 + level[head]
				queue.append(k)
				vertices += 1

	return level, vertices


q = int(input())
for case in range(q):
	e = input().split(" ")
	n = int(e[0])
	m = int(e[1])
	clib = int(e[2])
	croad = int(e[3])
	E = {}
	comp = 0
	edges_per_comp = []
	level = [-1]*(n+1)

	for i in range(1, n+1):
		E* = []

	for edge in range(m):
		e = input().split(" ")
		u = int(e[0])
		v = int(e[1])
		E.append(v)
		E[v].append(u)

	s = 1
	while True:
		flag = 0
		#vertices = 0
		level, vertices = bfs(s, n, E, level)
		#print(level)
		for i in range(1,n+1):
			if level* == -1:
				s = i
				flag = 1
				break
				
		edges_per_comp.append(vertices-1)
		if flag == 0:
			break;

	comp = len(edges_per_comp)
	#print(edges_per_comp)

	if clib < croad:
		print(clib*n)
	else:
		print(croad*sum(edges_per_comp)+comp*clib)