HackerRank Roads and Libraries Problem Solution

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
12

Explanation
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.

HackerRank Roads and Libraries Problem Solution

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)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python