Table of Contents
Roads and Libraries – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
1 Month Preparation Kit Solutions – HackerRank
C++ Roads and Libraries HackerRank Solution
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:67108864")
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <numeric>
#include <memory.h>
#include <time.h>
using namespace std;
typedef long long LL;
int q;
int n, m;
int road, lib;
vector<int> G[100000];
int used[100000];
int go(int v)
{
int res = 1;
used[v] = 1;
for (int i = 0; i < G[v].size(); ++i)
if (!used[G[v][i]])
res += go(G[v][i]);
return res;
}
int main()
{
scanf("%d", &q);
while (q-- > 0)
{
scanf("%d%d%d%d", &n, &m, &lib, &road);
for (int i = 0; i < n; ++i)
G[i].clear();
for (int i = 0; i < m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
memset(used, 0, sizeof(used));
LL res = 0;
for (int i = 0; i < n; ++i)
{
if (used[i])
continue;
int size = go(i);
res += lib + (LL)(size - 1) * min(road, lib);
}
printf("%lld\n", res);
}
return 0;
}
Java Roads and Libraries HackerRank Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution{
static int unionfind(int index,int [] parent)
{
while(index!=parent[index])
{
index=parent[index];
}
return index;
}
static void bfs( ArrayList<ArrayList<Integer>> list,int parent[], int size,int visited[],int v)
{
Queue<Integer> q=new LinkedList<>();
q.add(v); visited[v]=1;
while(!q.isEmpty())
{
int vertex=q.poll();
int lsize=list.get(vertex).size();
for(int i=0;i<lsize;++i)
{
int child=list.get(vertex).get(i);
if(visited[child]!=1)
{
q.add(child);
parent[child]=vertex;
visited[child]=1;
}
}
}
}
static void getParents( ArrayList<ArrayList<Integer>> list,int parent[], int size)
{
int visited[]=new int[size];
for(int i=0;i<size;++i)
{
if(visited[i]!=1)
bfs(list,parent,size,visited,i);
}
}
static long solve( ArrayList<ArrayList<Integer>> list, int size,int road_cost, int lib_cost)
{
int parent[]=new int[size];
for(int i=0;i<size;++i)
{
parent[i]=i;
}
getParents(list,parent,size);
int cost[]=new int[size]; long sum=0;
for(int i=0;i<size;++i)
{
int p=unionfind(i,parent); int count=0;
if(p==i)
{
++count;
}
else
{
if(road_cost+cost[p] >=lib_cost )
{
++count;
}
else
{
cost[i]=road_cost+cost[p];
sum+=(long)road_cost+cost[p];
}
}
sum+=(long)count*lib_cost;
}
return sum;
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int size=sc.nextInt();
int roads=sc.nextInt();
int lib_cost=sc.nextInt();
int road_cost=sc.nextInt();
ArrayList<ArrayList<Integer>> list=new ArrayList<>();
for(int i=0;i<size;++i)
{
list.add(new ArrayList<Integer>());
}
for(int i=0;i<roads;++i)
{
int p1=sc.nextInt()-1; int p2=sc.nextInt()-1;
list.get(p1).add(p2); list.get(p2).add(p1);
}
long minCost=solve(list,size,road_cost,lib_cost);
System.out.println(minCost);
System.gc();
}
sc.close();
}
}
Python 3 Roads and Libraries HackerRank Solution
from collections import defaultdict
from collections import deque
from math import pi,cos,sin
class graph:
def __init__(self):
self.nodes = []
self.edges = defaultdict(set)
def clone(self):
g = graph()
g.nodes = self.nodes[:]
for n in self.nodes:
for e in self.edges[n]:
g.edges[n].add(e)
return g
def count_clusters(g):
nclust = 0
used = set()
n = len(g.nodes)
csize = []
for node in g.nodes:
if node in used: continue
used.add(node)
size = 1
Q = deque()
Q.appendleft(node)
while Q:
cur = Q.pop()
for neigh in g.edges[cur]:
if neigh in used: continue
used.add(neigh)
Q.appendleft(neigh)
size += 1
nclust += 1
csize.append(size)
return nclust,csize
q = int(input())
for _ in range(q):
n,m,clib,croad = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for _ in range(m)]
if clib < croad:
print(clib*n)
continue
g = graph()
g.nodes = range(1,n+1)
for a,b in edges:
g.edges[a].add(b)
g.edges[b].add(a)
nc,cs = count_clusters(g)
print(nc*clib + sum((x-1)*croad for x in cs))
JavaScript Roads and Libraries HackerRank 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 x = parseInt(n_temp[2]);
var y = parseInt(n_temp[3]);
var forest = [];
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]);
if(!forest[city_1]){
forest[city_1] = [];
}
forest[city_1].push(city_2);
if(!forest[city_2]){
forest[city_2] = [];
}
forest[city_2].push(city_1);
}
//console.log(forest);
if(x<=y) {
console.log(n*x);
}
else {
var count = 0;
for(var i=1; i<=n; i++){
if(forest[i]==undefined){
count++;
}
if(!Array.isArray(forest[i])){
continue;
}
var c = ++count;
var que = [i];
while(que.length){//console.log(que);
var j = que.pop();
for(var k=0; k<forest[j].length; k++){
if(Array.isArray(forest[forest[j][k]]) && que.indexOf(forest[j][k])<0){
que.push(forest[j][k]);
}
//console.log(que);
}
forest[j] = count;
}
//console.log(forest);
}
console.log(x*count+(n-count)*y);
}
}
}
C Roads and Libraries HackerRank Solution
#include <stdio.h>
#define N 100000
int dsu[N];
int find(int i) {
return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (dsu[i] <= dsu[j]) {
dsu[i] += dsu[j];
dsu[j] = i;
} else {
dsu[j] += dsu[i];
dsu[i] = j;
}
}
int main() {
int q;
scanf("%d", &q);
while (q-- > 0) {
long long cost;
int n, m, cr, cl, i, j;
scanf("%d%d%d%d", &n, &m, &cl, &cr);
for (i = 0; i < n; i++)
dsu[i] = -1;
while (m-- > 0) {
scanf("%d%d", &i, &j);
i--, j--;
join(i, j);
}
cost = 0;
for (i = 0; i < n; i++) {
int r = find(i);
if (i == r) {
int cnt = -dsu[i];
cost += (long long) (cnt - 1) * cr + cl;
}
}
printf("%lld\n", cost < (long long) cl * n ? cost : (long long) cl * n);
}
return 0;
}
Leave a comment below
