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[i] = 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[i] = []
for edge in range(m):
e = input().split(" ")
u = int(e[0])
v = int(e[1])
E[u].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[i] == -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)