HackerRank | Дороги и библиотеки – Оптимизация кода

Я пытаюсь решить это Проблема с взломом, и некоторые из моих тестовых примеров не подтверждают, что окончательный ответ неверен. После прохождения предыдущего SO вопрос для той же проблемы, насколько я понимаю, HackerRank говорит, что ответ неверен, если код не выполняется в пределах памяти и времени. Я хотел бы знать, как я могу дополнительно оптимизировать свой код, чтобы уменьшить время выполнения и сложность пространства.

def roadsAndLibraries(n, c_lib, c_road, cities):
    
    # The arguments to the function above are number of nodes (n), cost of a library and road (c_lib, c_road) and cities connected by an edge (cities)
    graph = {}
    count = 0
    cc = []
    visited = set()
    
    
    #Adding all edges to create an Adjacency List using a dictionary
    for source,dest in cities:
        graph[source] = graph.get(source,[])+[dest]
        graph[dest] = graph.get(dest, []) + [source]
    #There is a weird condition in Hackerrank wherein the number of nodes (n) in the input can be greater than the max(cities). In that case, one needs to consider the additional nodes as an independent graph in a forest.
    if max(graph, key = int)<n:
        for i in range(max(graph, key = int)+1,n+1):
            graph[i]=[]
            
            
    # Generic Depth First Search         
    def depth_first_search(graph, visited, node, temp):
        if node not in visited:
            visited.add(node)
            temp.add(node)
            
            if node in graph:
                
                for neighbor in graph[node]:
                    
                    depth_first_search(graph, visited, neighbor, temp)
        return temp
    
        
    #Identify Connected Components using a Depth First Search.
    #These Connected Components will subsequentially used to calculate the cost    
    def connected_components(graph, visited):
        
        for key in graph:
            #print("Key = ", key)
            if key not in visited:
                temp = set()
                cc.append(depth_first_search(graph, visited, key, temp))
        return cc
    connected_components(graph, visited)
    
    
    #Return final cost over here
    cost = 0
                
    if c_road>c_lib:
        return n*c_lib
    else:
        for each in cc:
            cost += c_lib + (len(each)-1)*c_road
        return cost

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *