Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerRank Roads and Libraries problem solution

YASH PAL, 31 July 202410 September 2024

In this HackerRank Roads and Libraries Interview preparation kit problem, There are q queries, where each query consists of a map of HackerLand and value of c_lib and c_road. For each query, find the minimum cost to make libraries accessible to all citizens.

HackerRank Roads and Libraries Interview preparation kit solution

Problem solution in Python programming.

from collections import defaultdict
from collections import deque

from math import pi,cos,sin

class graph:
    def __init__(self):
        self.nodes = []
        self.edges = defaultdict(set)
    def clone(self):
        g = graph()
        g.nodes = self.nodes[:]
        for n in self.nodes:
            for e in self.edges[n]:
                g.edges[n].add(e)
        return g

def count_clusters(g):
    nclust = 0
    used = set()
    n = len(g.nodes)

    csize = []
    
    for node in g.nodes:
        if node in used: continue
        used.add(node)

        size = 1
        Q = deque()
        Q.appendleft(node)
        while Q:
            cur = Q.pop()
            for neigh in g.edges[cur]:
                if neigh in used: continue
                used.add(neigh)
                Q.appendleft(neigh)
                size += 1
        nclust += 1
        csize.append(size)

    return nclust,csize

q = int(input())


for _ in range(q):
    n,m,clib,croad = [int(x) for x in input().split()]
    edges = [[int(x) for x in input().split()] for _ in range(m)]

    if clib < croad:
        print(clib*n)
        continue
    
    g = graph()
    g.nodes = range(1,n+1)
    for a,b in edges:
        g.edges[a].add(b)
        g.edges[b].add(a)

    nc,cs = count_clusters(g)
    print(nc*clib + sum((x-1)*croad for x in cs))

Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

  public class Solution{
      static int unionfind(int index,int [] parent)
      {
        while(index!=parent[index])
        {
          index=parent[index];
        }
        return index;
      }
     
     static void bfs( ArrayList<ArrayList<Integer>> list,int parent[], int size,int visited[],int v)
     {
       Queue<Integer> q=new LinkedList<>();
       q.add(v); visited[v]=1;
       
       while(!q.isEmpty())
       {
        int vertex=q.poll();
        int lsize=list.get(vertex).size();
        for(int i=0;i<lsize;++i)
        {
          int child=list.get(vertex).get(i);
          if(visited[child]!=1)
          {
            q.add(child);
            parent[child]=vertex;
            visited[child]=1;
          }
        }
       }
       
     }
     
     static void getParents( ArrayList<ArrayList<Integer>> list,int parent[], int size)
     {
     int visited[]=new int[size];
      for(int i=0;i<size;++i)
      {     
          if(visited[i]!=1)
            bfs(list,parent,size,visited,i); 
      } 
    }
     
     static long solve( ArrayList<ArrayList<Integer>> list, int size,int road_cost, int lib_cost)
     {
        int parent[]=new int[size];
        for(int i=0;i<size;++i)
        {
          parent[i]=i;
        }
        getParents(list,parent,size);
        
        int cost[]=new int[size];  long sum=0;
        for(int i=0;i<size;++i)
        {
          int p=unionfind(i,parent); int count=0;
          if(p==i)
          {
            ++count;
          }
          else
          {
            if(road_cost+cost[p] >=lib_cost )
            {
              ++count;
            }
            else
            {
               cost[i]=road_cost+cost[p];
                sum+=(long)road_cost+cost[p];
            }    
          }
          sum+=(long)count*lib_cost;
        }
        return sum;
              
     }
    public static void main(String args[])
    {
      Scanner sc=new Scanner(System.in);
      int t=sc.nextInt();
      while(t-->0)
      {
      int size=sc.nextInt();
      int roads=sc.nextInt();
      int lib_cost=sc.nextInt();
      int road_cost=sc.nextInt();
      
      ArrayList<ArrayList<Integer>> list=new ArrayList<>();
      for(int i=0;i<size;++i)
      {
        list.add(new ArrayList<Integer>());
      }
      
      for(int i=0;i<roads;++i)
      {
        int p1=sc.nextInt()-1; int p2=sc.nextInt()-1;
        list.get(p1).add(p2); list.get(p2).add(p1);
      }
      
      long minCost=solve(list,size,road_cost,lib_cost);
      System.out.println(minCost);
      System.gc();
      }   
      sc.close();
    }
  }

Problem solution in C++ programming.

#define _CRT_SECURE_NO_WARNINGS

#pragma comment(linker, "/STACK:67108864")

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <numeric>
#include <memory.h>
#include <time.h>

using namespace std;

typedef long long LL;

int q;
int n, m;
int road, lib;

vector<int> G[100000];
int used[100000];

int go(int v)
{
	int res = 1;
	used[v] = 1;
	for (int i = 0; i < G[v].size(); ++i)
		if (!used[G[v][i]])
			res += go(G[v][i]);
	return res;
}

int main()
{
	scanf("%d", &q);
	while (q-- > 0)
	{
		scanf("%d%d%d%d", &n, &m, &lib, &road);
		for (int i = 0; i < n; ++i)
			G[i].clear();
		for (int i = 0; i < m; ++i)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			u--, v--;
			G[u].push_back(v);
			G[v].push_back(u);
		}

		memset(used, 0, sizeof(used));

		LL res = 0;
		for (int i = 0; i < n; ++i)
		{
			if (used[i])
				continue;
			int size = go(i);
			res += lib + (LL)(size - 1) * min(road, lib);
		}

		printf("%lldn", res);
	}
	return 0;
}

Problem solution in C programming.

#include <stdio.h>

#define N	100000

int dsu[N];

int find(int i) {
	return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (dsu[i] <= dsu[j]) {
		dsu[i] += dsu[j];
		dsu[j] = i;
	} else {
		dsu[j] += dsu[i];
		dsu[i] = j;
	}
}

int main() {
	int q;

	scanf("%d", &q);
	while (q-- > 0) {
		long long cost;
		int n, m, cr, cl, i, j;

		scanf("%d%d%d%d", &n, &m, &cl, &cr);
		for (i = 0; i < n; i++)
			dsu[i] = -1;
		while (m-- > 0) {
			scanf("%d%d", &i, &j);
			i--, j--;
			join(i, j);
		}
		cost = 0;
		for (i = 0; i < n; i++) {
			int r = find(i);

			if (i == r) {
				int cnt = -dsu[i];

				cost += (long long) (cnt - 1) * cr + cl;
			}
		}
		printf("%lldn", cost < (long long) cl * n ? cost : (long long) cl * n);
	}
	return 0;
}

Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var q = parseInt(readLine());
    for(var a0 = 0; a0 < q; a0++){
        var n_temp = readLine().split(' ');
        var n = parseInt(n_temp[0]);
        var m = parseInt(n_temp[1]);
        var x = parseInt(n_temp[2]);
        var y = parseInt(n_temp[3]);
        
        var forest = [];
        for(var a1 = 0; a1 < m; a1++){
            var city_1_temp = readLine().split(' ');
            var city_1 = parseInt(city_1_temp[0]);
            var city_2 = parseInt(city_1_temp[1]);
            
            if(!forest[city_1]){
                forest[city_1] = [];
            }
            forest[city_1].push(city_2);
            
            if(!forest[city_2]){
                forest[city_2] = [];
            }
            forest[city_2].push(city_1);
        }
        //console.log(forest);
        if(x<=y) {
            console.log(n*x);
        }
        else {

            var count = 0;
            for(var i=1; i<=n; i++){
                if(forest[i]==undefined){
                    count++;
                }
                if(!Array.isArray(forest[i])){
                    continue;
                }
                var c = ++count;
                var que = [i];
                while(que.length){//console.log(que);
                    var j = que.pop();
                    for(var k=0; k<forest[j].length; k++){
                        if(Array.isArray(forest[forest[j][k]]) && que.indexOf(forest[j][k])<0){
                            que.push(forest[j][k]);
                        }
                        //console.log(que);
                    }
                    forest[j] = count;
                }
                
                //console.log(forest);
            }
            
            console.log(x*count+(n-count)*y);
        }
    }

}

coding problems solutions interview prepration kit

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes