In this HackerRank Roads and Libraries Interview preparation kit problem, There are q 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 citizens.
Problem solution in Python programming.
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))Problem solution in Java Programming.
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();
}
}Problem solution in C++ programming.
#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;
}Problem solution in C programming.
#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;
}Problem solution in JavaScript programming.
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);
}
}
}
0 Comments