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

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.

• int n: integer, the number of cities
• int c_lib: integer, the cost to build a library
• 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):
city_1, city_2 = map(int, raw_input().strip().split(' '))

print(c_lib * num_cities)
else:
# Kruskal's algorithm
cities = []
for i in xrange(num_cities):
cities.append(Node(i))
MakeSet(cities[-1])
print(c_lib * len(connected_components) + c_road * num_roads)