You are not logged in. Please login at www.codechef.com to post your questions!

×

Roads and Libraries using Python

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

arijitdas's gravatar image

2★arijitdas
22
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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