In this post, we will solve HackerRank Roads and Libraries Problem Solution.
Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities. A citizen has access to a library if:
- Their city contains a library.
- They can travel by road from their city to a city containing a library.
Example
The following figure is a sample map of HackerLand where the dotted lines denote possible roads:
c_road = 2
c_lib = 3
cities = [[1, 7], [1, 3], [1, 2], [2, 3], [5, 6], [6, 8]]
The cost of building any road is cc_road = 2, and the cost to build a library in any city is c_lib = 3. Build 5 roads at a cost of 5 x 2 = 10 and 2 libraries for a cost of 6. One of the available roads in the cycle 1 →2→3 → 1 is not necessary.
There are a 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 the citizens.
Function Description
Complete the function roadsAndLibraries in the editor below.
roadsAndLibraries has the following parameters:
- int n: integer, the number of cities
- int c_lib: integer, the cost to build a library
- int c_road: integer, the cost to repair a road
- int cities[m][2]: each cities[i] contains two integers that represent cities that can be connected by a new road
Returns
-int: the minimal cost
Input Format
The first line contains a single integer q, that denotes the number of queries.
The subsequent lines describe each query in the following format:
-The first line contains four space-separated integers that describe the respective values of n m. c_lib and c_road, the number of cities, number of roads, cost of a library and cost of a
road.
-Each of the next m lines contains two space-separated integers, u[i] and v[i], that describe a bidirectional road that can be built to connect cities u[i] and v[i].
Sample Input
STDIN Function
----- --------
2 q = 2
3 3 2 1 n = 3, cities[] size m = 3, c_lib = 2, c_road = 1
1 2 cities = [[1, 2], [3, 1], [2, 3]]
3 1
2 3
6 6 2 5 n = 6, cities[] size m = 6, c_lib = 2, c_road = 5
1 3 cities = [[1, 3], [3, 4],...]
3 4
2 4
1 2
2 3
5 6
Sample Output
4
12Explanation
Perform the following q = 2 queries:
- HackerLand contains n = 3 cities and can be connected by m = 3 bidirectional roads. The price of building a library is cb = 2 and the price for repairing a road is Croad = 1.
The cheapest way to make libraries accessible to all is to:
- Build a library in city 1 at a cost of x = 2.
- Build the road between cities 1 and 2 at a cost of y = 1.
- Build the road between cities 2 and 3 at a cost of y = 1.
This gives a total cost of 2+1+1 = 4. Note that the road between cities 3 and 1 does not need to be built because each is connected to city 2.
- In this scenario it is optimal to build a library in each city because the cost to build a library is less than the cost to build a road.
There are 6 cities, so the total cost is 6 x 2 = 12.
Roads and Libraries C Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
typedef struct city_list {
int city;
struct city_list *next;
} c_list ;
typedef struct city_s{
bool seen;
c_list *neighbors;
} city ;
unsigned long traverse_neighbors (city *city_a, int start, int c_road) {
unsigned long sum = 0;
c_list *neighbor = city_a[start].neighbors;
while (neighbor != NULL)
{
if (city_a[neighbor->city].seen == false)
{
city_a[neighbor->city].seen = true;
sum += c_road;
sum += traverse_neighbors(city_a, neighbor->city, c_road);
}
neighbor=neighbor->next;
}
return sum;
}
unsigned long long traverse_city(city *city_a, int num_c, int num_r, int c_lib, \
int c_road) {
unsigned long long sum = 0;
for (int i=1; i <= num_c; i++)
{
if (city_a[i].seen == true)
continue;
else
city_a[i].seen = true;
// pay for a new library, and find all attached neighbors
sum += c_lib;
sum += traverse_neighbors(city_a, i, c_road);
}
return sum;
}
void insert_neighbor (city *city_a, int city_1, int city_2) {
c_list *tempneighbor ;
if (city_a[city_1].neighbors == NULL) {
// First city.neighbors hasn't been created yet.
city_a[city_1].neighbors = (c_list *)(calloc (sizeof (c_list), 1));
city_a[city_1].neighbors->city = city_2;
} else {
tempneighbor = (c_list *)(calloc (sizeof ( c_list), 1));
tempneighbor->city = city_2;
// insert at head.
tempneighbor->next = city_a[city_1].neighbors;
city_a[city_1].neighbors = tempneighbor;
}
}
void free_city(city *city_a, int array_size)
{
c_list *temp1, *temp2;
for(int i=0; i <= array_size; i++)
{
temp1 = city_a[i].neighbors;
while( temp1 != NULL )
{
temp2 = temp1;
temp1 = temp1->next;
free(temp2);
}
}
free (city_a);
}
int main() {
int q;
scanf("%d",&q);
for(int a0 = 0; a0 < q; a0++){
unsigned long num_cities;
unsigned long num_roads;
unsigned long c_lib;
unsigned long c_road;
city *city_a;
scanf("%lu %lu %lu %lu",&num_cities,&num_roads,&c_lib,&c_road);
// Allocate city array
city_a= (city *) calloc(sizeof (city), (num_cities + 1));
for(int a1 = 0; a1 < num_roads; a1++){
int city_1;
int city_2;
scanf("%d %d",&city_1,&city_2);
insert_neighbor (city_a, city_1, city_2);
insert_neighbor (city_a, city_2, city_1);
}
// if libraries cheaper than roads.. It's cheaper to give each city
// it's own library
if (c_lib <= c_road)
{
printf("%lu\n", c_lib*num_cities);
}
else
{
unsigned long long result = traverse_city(city_a, num_cities, num_roads, c_lib, c_road);
printf("%llu\n", result);
}
free_city(city_a, num_cities);
}
return 0;
}Roads and Libraries C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100005;
typedef long long ll;
int n,m;
ll cr,cl;
int pnt[maxn];
int pd(int x){
if(x!=pnt[x])pnt[x]=pd(pnt[x]);
return pnt[x];
}
struct P{
int x,y;
ll z;
P(){}
P(int x,int y,ll z):x(x),y(y),z(z){}
bool operator<(const P&a)const{
return z<a.z;
}
};
vector<P>e;
int main() {
// freopen("in.cpp","r",stdin);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin>>T;
while(T--){
cin>>n>>m>>cl>>cr;
for(int i=0;i<=n;i++)pnt[i]=i;
e.clear();
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
e.push_back(P(x,y,cr));
}
for(int i=1;i<=n;i++)e.push_back(P(0,i,cl));
ll ret=0;
sort(e.begin(),e.end());
for(int i=0;i<e.size();i++){
int x=pd(e[i].x);
int y=pd(e[i].y);
if(x==y)continue;
pnt[x]=y;
ret+=e[i].z;
}
cout<<ret<<endl;
}
return 0;
}Roads and Libraries C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static int clib,croad;
static int n,m;
static HashSet<int>[] g;
static Dictionary<int, HashSet<int>> regions;
static int[] ds;
static int[] cc;
static void Main(String[] args) {
int q = Convert.ToInt32(Console.ReadLine());
for(int a0 = 0; a0 < q; a0++)
{
string[] tokens_n = Console.ReadLine().Split(' ');
n = int.Parse(tokens_n[0]);
m = int.Parse(tokens_n[1]);
clib = int.Parse(tokens_n[2]);
croad = int.Parse(tokens_n[3]);
ds = new int[n+1];
cc = new int[n+1];
for (int i=0; i<ds.Length; i++)
ds[i] = i;
g = Enumerable.Range(0,n+1).Select(k=>new HashSet<int>()).ToArray();
for(int a1 = 0; a1 < m; a1++){
string[] tokens_city_1 = Console.ReadLine().Split(' ');
int city_1 = int.Parse(tokens_city_1[0]);
int city_2 = int.Parse(tokens_city_1[1]);
g[city_1].Add(city_2);
g[city_2].Add(city_1);
Union(ds, city_1, city_2);
}
regions = new Dictionary<int, HashSet<int>>();
int count = 0;
for (int i=1; i<ds.Length; i++)
{
var root = Find(ds, i);
if (!regions.ContainsKey(root)) regions[root] = new HashSet<int>();
regions[root].Add(i);
}
long cost = 0;
foreach(var r in regions.Values)
cost += Search(r);
Console.WriteLine(cost);
}
}
public static long Search(HashSet<int> region)
{
int count = region.Count;
if (region.Count==1) return clib;
long cost = 0;
if (croad < clib)
{
// All roads connected, 1 library
cost = clib + (count-1) * croad;
}
else
{
// No roads connect, n librarys
cost = clib * count;
}
return cost;
}
public static bool Union(int[] ds, int a, int b)
{
int ra = Find(ds, a);
int rb = Find(ds, b);
if (ra == rb)
return false;
if (ra < rb) ds[rb] = ra;
else ds[ra] = rb;
return true;
}
public static int Find(int[] ds, int a)
{
int r = ds[a];
if (r != a)
ds[a] = r = Find(ds, r);
return r;
}
}Roads and Libraries Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'roadsAndLibraries' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER c_lib
* 3. INTEGER c_road
* 4. 2D_INTEGER_ARRAY cities
*/
private static class Node{
public int id;
public List<Node> Adjecents = new ArrayList<>();
public Node(int id){
this.id=id;
}
}
public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
// Write your code here
int n_roads = cities.size();
ArrayList<Node> Graph = new ArrayList<>(n+1);
for(int i =0;i<=n;i++){
Graph.add(new Node(i));
}
for(int i =0;i<n_roads;i++){
List<Integer> city = cities.get(i);
Integer city1 = city.get(0);
Integer city2 = city.get(1);
Graph.get(city1).Adjecents.add(Graph.get(city2));
Graph.get(city2).Adjecents.add(Graph.get(city1));
}
boolean[] visited = new boolean[n+1];
Arrays.fill(visited,false);
ArrayList<Long> graphcost = new ArrayList<>();
for(int i =1;i<=n;i++){
if(!visited[i]&&Graph.get(i).Adjecents.size()>0){
graphcost.add(dfs(Graph.get(i),visited));
} else if(Graph.get(i).Adjecents.size()==0)
graphcost.add(1L);
}
long result =0;
for(int i =0;i<graphcost.size();i++){
result+=Math.min((graphcost.get(i)-1)*c_road + c_lib,graphcost.get(i)*c_lib);
}
return result;
}
private static long dfs(Node city, boolean[] visited){
visited[city.id] = true;
long cost =1;
for(int i =0;i<city.Adjecents.size();i++){
if(!visited[city.Adjecents.get(i).id]){
cost += dfs(city.Adjecents.get(i),visited);
}
}
return cost;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, q).forEach(qItr -> {
try {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
int c_lib = Integer.parseInt(firstMultipleInput[2]);
int c_road = Integer.parseInt(firstMultipleInput[3]);
List<List<Integer>> cities = new ArrayList<>();
IntStream.range(0, m).forEach(i -> {
try {
cities.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
long result = Result.roadsAndLibraries(n, c_lib, c_road, cities);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}Roads and Libraries JavaScript Solution
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 lib = parseInt(n_temp[2]);
var road = parseInt(n_temp[3]);
// In case roads and more expensive or equal to library price
// Build a library in each city and skip over the node connections
if (road >= lib) {
input_currentline += m;
console.log(n * lib);
continue;
}
// Build the data structure, array of array
var nodes = [];
for (var i = 1; i <= n; i++) {
nodes[i] = [];
}
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]);
nodes[city_1].push(city_2);
nodes[city_2].push(city_1);
}
// Go over all the nodes and conduct a BFS
// If a node is never seen build a library
// If a node is reached through a connection and never seen build a road
var cost = 0;
var passedOver = [];
for (var i = 1; i <= n; i++) {
if (passedOver[i]) {
continue;
}
passedOver[i] = true;
cost += lib;
var queue = [];
queue.push(i);
while (queue.length > 0) {
var nodeIdx = queue.shift();
var connections = nodes[nodeIdx];
for (var w = 0; w < connections.length; w++) {
if (passedOver[connections[w]]) {
continue;
}
passedOver[connections[w]] = true;
queue.push(connections[w]);
cost += road;
}
}
}
console.log(cost);
}
}Roads and Libraries Python Solution
#!/bin/python3
import sys
q = int(input().strip())
def SPT(visited, city,graph,y):
visited.add(city)
que = [city]
cost = 0
while len(que) != 0:
node = que.pop(0)
for c in graph[node]:
if c not in visited:
visited.add(c)
cost += y
que.append(c)
return cost
for a0 in range(q):
n,m,x,y = input().strip().split(' ')
n,m,x,y = [int(n),int(m),int(x),int(y)]
graph = [[] for _ in range(n+1)]
for a1 in range(m):
city_1,city_2 = input().strip().split(' ')
city_1,city_2 = [int(city_1),int(city_2)]
graph[city_1].append(city_2)
graph[city_2].append(city_1)
if y > x:
print (n*x)
continue
else:
visited = set()
cost = 0
for i in range(1, n+1):
if i not in visited:
cost += x + SPT(visited, i, graph, y)
print (cost)
