HackerRank Roads and Libraries problem solution

YASH PAL,

In this HackerRank Roads and Libraries Interview preparation kit problem solution, Determine the minimum cost to provide library access to all citizens of HackerLand. There are n cities numbered from 1 to n. Currently there are no libraries and the cities are not connected. Bidirectional roads may be built between any city pair listed in cities. A citizen has access to a library if:

  • They can travel by road from their city to a city containing a library.
  • Their city contains a library.
HackerRank Roads and Libraries Interview preparation kit solution

HackerRank Roads and Libraries problem solution in Python.

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

Roads and Libraries problem solution in Java.

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("%lldn", 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("%lldn", 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);
        }
    }

}

coding problems solutions Hackerrank Problems Solutions interview prepration kit