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

  • taffeAlexander
     + 0 comments

    After thinking about it here is my solution in pseudocode then python:

    My Intuition: Cities that can be connected by roads make up an island or a sub graph. Each island only needs 1 library + the cost of the roads between the cities. So you can count the number of islands + the number of roads on each island. However the cost of a road can be so high that it's cheaper to build a library in each city. I had to think about this for a bit, I thought it might be some kind of greedy problem so I tried to break it down. I thought about when 1 road cost < 1 lib cost, 1 road cost == 1 lib cost and 1 road cost > 1 lib cost. Turns out if the cost of building a road is >= the cost of building a library, it makes more sense to put a library in each city (I did the math with the 2 cities 1 road case). So at the end of the day you just have to compare building roads + libraries (one each island) or just building libraries in each city. Also another key point is each road is bi-directional so if you build an adjacency list you have to add edges in both directions.

    Psuedocode:

        1. Build adjacency list (with bi-directional edges).
    2. For each city:
        if not visited city add 1 library and start a Breadth First Search starting from this city (new island).
    bfs:
        each city visited = 1 new road, skip cities already visited, add each city visited to list of visited cities.
    3. return min(num_cities * lib_cost, cities_and_roads_cost)

    # BFS - O(V + E) - Time | O(2 * E) - Space
def get_roads_from_city(graph, city, visited):
    num_roads = 0
    neighbor_q = []
    visited.add(city)
    for neighbor in graph[city]:
        neighbor_q.append(neighbor)
    while len(neighbor_q) > 0:
        node = neighbor_q.pop(0)
        if node not in visited:
            num_roads += 1
            visited.add(node)
            if node in graph:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        neighbor_q.append(neighbor)
    return num_roads, visited


def roadsAndLibraries(n, c_lib, c_road, cities):
    # Write your code here
    if n == 1:
        return c_lib
    
    graph = {}
    # Build Adjacency List
    for city in cities:
        neighbors = graph.get(city[0], [])
        neighbors.append(city[1])
        graph[city[0]] = neighbors
        
        neighbors = graph.get(city[1], [])
        neighbors.append(city[0])
        graph[city[1]] = neighbors
    
    for city in range(1, n + 1):
        if city not in graph:
            graph[city] = []
    
    # BFS
    def libraries_and_roads_cost(graph):
        num_roads = 0
        num_libraries = 0
        visited = set()
        for city in graph.keys():
            if city not in visited:
                roads, visited = get_roads_from_city(graph, city, visited)
                num_roads += roads
                num_libraries += 1
        return num_libraries * c_lib + num_roads * c_road
    
    libs_only = n * c_lib
    libs_roads = libraries_and_roads_cost(graph)
    return min(libs_only, libs_roads)