Discussion on Roads and Libraries Challenge

2 years ago+ 0 comments

the solution involves build the graph and then find the connected components the mininum edges to connect all the nodes in a graph is the total of nodes - 1 the cost of the roads is the number of edges - 1 * cost of the road And for each graph component we need to add a library

def dfs(visited, graph, node):
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
    return visited


def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib <= c_road:
        return c_lib * n
    # build the graph
    graph = {}
    for i in range(1, n + 1):
        graph[i] = []

    for city in cities:
        graph[city[0]].append(city[1])
        graph[city[1]].append(city[0])

    # split graphs into components
    graph_components = set()
    for node in range(1, n + 1):
        graph_elements = dfs(set(), graph, node)
        if graph_elements not in graph_components:
            graph_components.add(frozenset(graph_elements))
    print(f"graph_components: {graph_components}")

    # calculate the cost
    cost_road = 0
    lib_cost = 0
    for i in graph_components:
        cost_road += c_road * (len(i) - 1)
        lib_cost += c_lib
    print(f"cost_road: {cost_road}, lib_cost: {lib_cost}")
    return cost_road + lib_cost

Cookie support is required to access HackerRank