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 →

  • niharikamotur929
    4 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
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy