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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Roads and Libraries
  5. Discussions

Roads and Libraries

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 833 Discussions, By:

recency

Please Login in order to post a comment

  • preeti_213
    5 days ago+ 0 comments

    JAVA 8

    public static long roadsAndLibraries(int vertices, int c_lib, int c_road, List> cities) { //base case if(c_lib

    //arraylist for adjacency list
    ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
    for(int i = 0;i<vertices;i++)
    {
        arr.add(new ArrayList<Integer>());
    }
    //adding edges --> adjacency list
    for(int i = 0;i<cities.size();i++)
    {
        arr.get(cities.get(i).get(0)-1).add(cities.get(i).get(1)-1);
        arr.get(cities.get(i).get(1)-1).add(cities.get(i).get(0)-1);
    }
    
    boolean[] visited = new boolean[vertices];
    
    long cost = (long)vertices*c_lib; 
    long road = 0;
    
    for(int i = 0;i<vertices;i++)
    {
        if(!visited[i])
        {
            road += connectedRoads(i,arr,visited);
            long tempc = ((long)vertices - road)*(long)c_lib + road*(long)c_road;
            cost = Math.min(cost, tempc);
        }
    } 
    return cost;
    
    }
    private static long connectedRoads(int source,ArrayList<ArrayList<Integer>> arr, boolean[] visited) 
    {
        long roads = 0;
        visited[source] = true;
    
        //using bfs
        Queue<Integer> q = new LinkedList();
        q.offer(source);
    
        while(!q.isEmpty())
        {
            int current = q.poll();
            for(int next : arr.get(current))
            {
                if(visited[next]!= true)
                {
                    visited[next]=true;
                    roads++;
                    q.add(next);
                }
            }
        }
        return roads;
    }
    
    0|
    Permalink
  • austinthomasarm1
    2 weeks ago+ 0 comments

    C++ Solution DFS FUNC

    long dfs(map<int,vector<int>> &paths, vector<bool> &visited, int current){
        // initialize node count to 1
        int node_count = 1;
        // set this current position in the visited array to true
        visited[current] = true;
    
        // iterate through the paths and dfs all non visited nodes/integers
        for(auto it = paths[current].begin();it!=paths[current].end();it++){
            if(!visited[*it]){
                // add the return value of dfs to the node count
                node_count += dfs(paths,visited,*it);
            }
        }
    return node_count;
    }
    

    roadsAndLibraries FUNC

    long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) {
        // initialize answer
        long long answer            = 0;
        long long extra_costs       = 0;
        long long total_components  = 0;
        // rename constants
        int cost_library        = c_lib;
        int cost_road           = c_road;
        int number_cities       = n;
        int paths_given         = cities.size();
    
        // build our adjacency map, bidirectional
        map<int,vector<int>> paths;    
            for(int i=0;i<cities.size();i++){
                int x = cities[i][0];
                int y = cities[i][1];            
                    paths[x].push_back(y);
                    paths[y].push_back(x);
            }
        // build our visited vector, initialize to false
        vector<bool>    visited(n,false);
        // iterate over the adjacency map and 
        for(auto it=paths.begin();it!=paths.end();it++){
            if(!visited[it->first]){
                int component_size = dfs(paths,visited,it->first);
                total_components += component_size;
                answer += min((((component_size-1)*(cost_road))+(cost_library)),((component_size)*(cost_library)));
            }
        }
        
        if(n>total_components){
            extra_costs = (n-total_components)*cost_library;
        }
        
    return answer+extra_costs;
    }
    
    0|
    Permalink
  • guilherme_beira
    4 weeks 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
    
    0|
    Permalink
  • CodeName777
    2 months ago+ 0 comments

    https://medium.com/p/3b035eb9e9f1

    -2|
    Permalink
  • niharikamotur929
    2 months ago+ 1 comment

    Some of my test cases are failing due to Wrong Answer. Could anyone please let me know where I am going wrong

    `

    static Integer findParent(int node, List parent){ if(node == parent.get(node)){ return node; }

        return parent.set(parent.get(node), findParent(parent.get(node), parent));
    }
    
    static void union(int u, int v, List<Integer> parent, List<Integer> rank){
        int pu = findParent(u, parent);
        int pv = findParent(v, parent);
    
        if(rank.get(pu) > rank.get(pv)) {
            parent.set(pv, pu);
        }else if(rank.get(pu) < rank.get(pv)) {
            parent.set(pu, pv);
        }else {
            parent.set(pv, pu);
            rank.set(pu, rank.get(pu) + 1);
        }
    }
    
    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
    
        List<Integer> parent = new ArrayList<>();
        List<Integer> rank = new ArrayList<>();
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        long result = 0;
    
        for(int i = 0; i <= n; i++){
            parent.add(i);
            rank.add(0);
        }
    
        for(int i = 0; i< cities.size(); i++){
            int u = cities.get(i).get(0);
            int v = cities.get(i).get(1);
            union(u, v, parent, rank);
        }
    
        for(int i = 1; i <= n; i++){
            Integer fp = findParent(i, parent);
            freqMap.put(fp, freqMap.getOrDefault(fp, 0) + 1);
        }
    
        for(Integer val: freqMap.values()){
            result += Math.min((long)val * c_lib, ((long)(val - 1) * c_road) + c_lib);
        }
    
        return result;
    }
    

    }`

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy