Roads and Libraries HackerRank Solution in C, C++, Python

by

Determine the minimum cost to provide library access to all citizens of HackerLand. There are  cities numbered from  to . Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in . 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:

The cost of building any road is , and the cost to build a library in any city is . Build  roads at a cost of  and  libraries for a cost of . One of the available roads in the cycle  is not necessary.

There are  queries, where each query consists of a map of HackerLand and value of  and . 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  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 , 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 , ,  and , the number of cities, number of roads, cost of a library and cost of a road.
– Each of the next  lines contains two space-separated integers,  and , that describe a bidirectional road that can be built to connect cities  and .

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  queries:

  1. HackerLand contains  cities and can be connected by  bidirectional roads. The price of building a library is  and the price for repairing a road is .The cheapest way to make libraries accessible to all is to:
    • Build a library in city  at a cost of .
    • Build the road between cities  and  at a cost of .
    • Build the road between cities  and  at a cost of .

    This gives a total cost of . Note that the road between cities  and  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  cities, so the total cost is .

Roads and Libraries HackerRank Solution in C

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int q; 
    scanf("%d",&q);
    for(int a0 = 0; a0 < q; a0++){
        int n; 
        int m; 
        int x; 
        int y; 
        scanf("%d %d %d %d",&n,&m,&x,&y);
        if(x<=y){
            for(int a1 = 0; a1 < m; a1++){
                int city_1; 
                int city_2; 
                scanf("%d %d",&city_1,&city_2);
            }
            printf("%ld\n",(long)x*n);
            continue;
        }else{
            int graph[n+1], ans=0;
            for(int i=1; i<=n; i++){
                graph[i]=i;
            }
            for(int a1 = 0; a1 < m; a1++){
                int city_1; 
                int city_2; 
                int ht_1=0, ht_2=0;
                scanf("%d %d",&city_1,&city_2);
                while(graph[city_1]!=city_1){
                    graph[city_1]=graph[graph[city_1]];
                    city_1=graph[city_1];
                    ht_1++;
                }
                while(graph[city_2]!=city_2){
                    graph[city_2]=graph[graph[city_2]];
                    city_2=graph[city_2];
                    ht_2++;
                }
                if(ht_1>=ht_2) graph[city_1]=city_2;
                else graph[city_2]=city_1;
            }
            
            for(int i=1; i<=n; i++){
                if(graph[i]==i) ans++;
            }
            printf("%ld\n",(long)x*ans+((long)n-ans)*(long)y);
        }
        
        
        
    }
    return 0;
}

Roads and Libraries HackerRank Solution in CPP

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int data[125252];
inline void init(){
  REP(i,125252)data[i]=-1;
}
int root(int x){
  return data[x]<0?x:data[x]=root(data[x]);
}
int unite(int x,int y){
  x=root(x);y=root(y);
  if(x==y)return 0;
  if(data[x]>data[y])swap(x,y);
  data[x]+=data[y];
  data[y]=x;
  return 1;
}

int n,m;
int cr,cl;
pii es[125252];
void solve(){
  scanf("%d%d%d%d",&n,&m,&cl,&cr);
  int sz = n;
  init();
  ll ans = (ll)cl*n;
  REP(i,m){
    int x,y;
    scanf("%d%d",&x,&y);
    --x;--y;
    if(unite(x,y)){
      sz--;
      CHMIN(ans,(ll)cl*sz + (ll)cr*(n-sz));
    }
  }
  printf("%lld\n",ans);
}

int main(){
  int q;
  scanf("%d",&q);
  while(q--)solve();
  return 0;
}

Roads and Libraries HackerRank Solution in CPP

#!/bin/python

import sys

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

def MakeSet(x):
    x.parent = x
    x.rank   = 0

def Union(x, y):
    xRoot = Find(x)
    yRoot = Find(y)
    if xRoot.rank > yRoot.rank:
        yRoot.parent = xRoot
    elif xRoot.rank < yRoot.rank:
        xRoot.parent = yRoot
    elif xRoot != yRoot: # Unless x and y are already in same set, merge them
        yRoot.parent = xRoot
        xRoot.rank = xRoot.rank + 1

def Find(x):
    if x.parent == x:
        return x
    else:
        x.parent = Find(x.parent)
        return x.parent

q = int(raw_input().strip())
for _ in xrange(q):
    num_cities, num_roads, c_lib, c_road = map(int, raw_input().strip().split(' '))
    roads = []
    for _ in xrange(num_roads):
        city_1, city_2 = map(int, raw_input().strip().split(' '))
        roads.append((city_1, city_2))
    
    if c_lib <= c_road:
        print(c_lib * num_cities)
    else:
        # Kruskal's algorithm
        num_roads = 0
        cities = []
        for i in xrange(num_cities):
            cities.append(Node(i))
            MakeSet(cities[-1])
        for (city_1, city_2) in roads:
            city_1 = cities[city_1 - 1]
            city_2 = cities[city_2 - 1]
            if Find(city_1) != Find(city_2):
                Union(city_1, city_2)
                num_roads += 1
        connected_components = set()
        for i in xrange(num_cities):
            connected_components.add(Find(cities[i]))
        print(c_lib * len(connected_components) + c_road * num_roads)

Leave a Comment