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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • guilherme_beira
    3 months 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
    
    1|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy