We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

  • guilherme_beira
     + 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