×

# Roads and Libraries using Python

 0 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)  asked 19 Jul '18, 00:23 2●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,409
×798
×529
×513
×374
×310
×281
×195

question asked: 19 Jul '18, 00:23

question was seen: 194 times

last updated: 19 Jul '18, 00:23