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:

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

- 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)

Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.