You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank Roads and Libraries Solution

Hackerrank Roads and Libraries Solution

Beeze Aal
Beeze Aal

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.

HackerLand has  cities numbered from  to . The cities are connected by  bidirectional roads. 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.

The following figure is a sample map of HackerLand where the dotted lines denote obstructed roads:

image

The cost of repairing any road is  dollars, and the cost to build a library in any city is  dollars.  If in the above example  and , we would build  roads at a cost of  and  libraries for a cost of .  We don't need to rebuild one of the roads in the cycle .

You are given  queries, where each query consists of a map of HackerLand and value of  and . For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.

Function Description

Complete the function roadsAndLibraries in the editor below.  It must return the minimal cost of providing libraries to all, as an integer.

roadsAndLibraries has the following parameters:

  • n: integer, the number of cities
  • c_lib: integer, the cost to build a library
  • c_road: integer, the cost to repair a road
  • cities: 2D array of integers where each ¬†contains two integers that represent cities connected by an obstructed road .

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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 connects cities  and .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

  • Each road connects two distinct cities.

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For each query, print an integer that denotes the minimum cost to make libraries accessible to all the citizens on a new line.

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6

Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

4
12

Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Perform the following  queries:

HackerLand contains  cities connected by  bidirectional roads. The price of building a library is  and the price for repairing a road is .

image

The cheapest way to make libraries accessible to all is to:

  • Build a library in city ¬†at a cost of .
  • Repair the road between cities ¬†and ¬†at a cost of .
  • Repair 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 repaired each is connected to city .

In this scenario it is optimal to build a library in each city because the cost of building a library () is less than the cost of repairing a road ().

image

There are  cities, so the total cost is .

Solution in java8

Approach 1.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

 	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int q = in.nextInt();
		for(int a0 = 0; a0 < q; a0++){
			int n = in.nextInt();
			Graph g=new Graph(n,false);
			int m = in.nextInt();
			int clib = in.nextInt();
			int croad = in.nextInt();
			for(int a1 = 0; a1 < m; a1++){
				int city_1 = in.nextInt();
				int city_2 = in.nextInt();
				g.insertEdge(city_1-1,city_2-1);
			}
			System.out.println(getCost(g,clib,croad));
		}
	}
	private static long getCost(Graph g,long  clib,long  croad){
		if(clib<croad){
			return clib*g.v;
		}
		boolean visited[]=new boolean[g.v];
		long cost=0;
		for(int i=0;i<g.v;i++){
			if(!visited[i]){
				int x=DFSUtil(g,visited,i);
				cost+=(x-1)*croad;
				cost+=clib;
			}
		}
		return cost;
	}
	private static int DFSUtil(Graph g,boolean visited[],int current){
		int count=1;
		visited[current]=true;
		for(int a:g.list[current]){
			if(!visited[a]){
				count+=DFSUtil(g,visited,a);
			}
		}
		return count;
	}
}
class Graph {
	int v;
	LinkedList<Integer> list[];
	private final boolean directed;
	/** Constructor of Graph, takes no. of vertex and boolean value to specify whether graph is directed or not */
	Graph(int v,boolean directed){
		this.v=v;
		this.directed=directed;
		list=new LinkedList[v];
		for(int i=0;i<v;i++){
			list[i]=new LinkedList<Integer>();
		}
	}

	/* vertex numbering start with 0 as well as adjacency list no. start with 0 */

	public void insertEdge(int a,int b){
		list[a].add(b);
		if(!directed){
			list[b].add(a);
		}
	}
}

Approach 2.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static long roadsAndLibraries(int x, int y) {
        long cost = 0;
        
        for (int i = 0; i < adj.size(); i++) {
            if (!visited[i]) {
                count = 0;
                dfs(i);
                if (x > y) {
                    cost += x + y * (count - 1); 
                } else {
                    cost += x * count;
                }
            }
        }
        
        return cost;
    }
    
    static void dfs(int i) {
        visited[i] = true;
        count++;
        
        List<Integer> list = adj.get(i);
        for (int j = 0; j < list.size(); j++) {
            if (!visited[list.get(j)]) {
                dfs(list.get(j));
            }
        }
    }
    
    private static List<List<Integer>> adj;
    private static boolean[] visited;
    private static int count;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            
            adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            visited = new boolean[n];
            
            int m = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            
            for(int a1 = 0; a1 < m; a1++){
                int city_1 = in.nextInt();
                int city_2 = in.nextInt();
                adj.get(city_1 - 1).add(city_2 - 1);
                adj.get(city_2 - 1).add(city_1 - 1);
            }
            
            System.out.println(roadsAndLibraries(x, y));
        }
        in.close();
    }
}

Approach 3.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
    private static List<List<Integer>> adj;
    private static boolean[] visited;
    private static int count;

    public static void main(String[] args) {      
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            
            adj = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            visited = new boolean[n];
            
            int m = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            for(int a1 = 0; a1 < m; a1++){
                int city_1 = in.nextInt();
                int city_2 = in.nextInt();
                adj.get(city_1 - 1).add(city_2 - 1);
                adj.get(city_2 - 1).add(city_1 - 1);
            }
            
            System.out.println(roadsAndLibraries(x, y));
        }
        
        in.close();
    }
    
    private static long roadsAndLibraries(int x, int y) {
        long cost = 0;
        
        for (int i = 0; i < adj.size(); i++) {
            if (!visited[i]) {
                count = 0;
                dfs(i);
                if (x > y) {
                    cost += x + y * (count - 1);
                } else {
                    cost += x * count;
                }
            }
        }
        
        return cost;
    }
    
    private static void dfs(int i) {
        visited[i] = true;
        count++;
        
        List<Integer> list = adj.get(i);
        for (int j = 0; j < list.size(); j++) {
            if (!visited[list.get(j)]) {
                dfs(list.get(j));
            }
        }
    }
}

Solution in python3

Approach 1.

#!/bin/python3

def dfs(graph, start, visited):
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)

def roadsAndLibraries(n, cLib, cRoad, cities):
    # construct graph as adjacency-list
    graph = {i: set() for i in range(1,n+1)}
    for city1, city2 in cities:
        graph[city1].add(city2)
        graph[city2].add(city1)

    # if libraries are cheaper than roads, build 
    #   library in every city and build no roads
    if cLib < cRoad:
        return cLib * n

    # determine number of connected components (CC) in graph
    visited = set()
    nCC = 0
    for city in range(1, n+1):
        if city not in visited:
            dfs(graph, city, visited)
            nCC += 1

    # 1 library per CC, nCitiesPerCC-1 roads per CC
    return nCC*cLib + (n-nCC)*cRoad

if __name__ == '__main__':
    q = int(input())

    for _ in range(q):
        n, m, cLib, cRoad = map(int, input().split())
        cities = []
        for _ in range(m):
            cities.append(list(map(int, input().split())))

        result = roadsAndLibraries(n, cLib, cRoad, cities)
        print(result)

Approach 2.

#!/bin/python3

import math
import os
import random
import re
import sys

from collections import defaultdict

def build_graph(n, cities):
    g = defaultdict(set)
    
    for x, y in cities:
        g[x].add(y)
        g[y].add(x)
    
    return g

def get_cc_sizes(g, n):
    visited = set()
    sizes = []

    for i in range(1, n+1):
        if i in visited:
            continue

        visited.add(i)
        cc_size = 1

        to_visit = set(g[i])
        while to_visit:
            j = to_visit.pop()

            if j in visited:
                continue
            visited.add(j)

            cc_size += 1
            to_visit.update(g[j])

        sizes.append(cc_size)

    return sizes

def cc_cost(size, c_road, c_lib):
    assert size > 0
    return (size - 1) * c_road + c_lib

# Complete the roadsAndLibraries function below.
def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib < c_road:
        return n * c_lib

    g = build_graph(n, cities)
    cc_sizes = get_cc_sizes(g, n)

    cost = sum(cc_cost(size, c_road, c_lib) for size in cc_sizes)

    return cost

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        nmC_libC_road = input().split()

        n = int(nmC_libC_road[0])

        m = int(nmC_libC_road[1])

        c_lib = int(nmC_libC_road[2])

        c_road = int(nmC_libC_road[3])

        cities = []

        for _ in range(m):
            cities.append(list(map(int, input().rstrip().split())))

        result = roadsAndLibraries(n, c_lib, c_road, cities)

        fptr.write(str(result) + '\n')

    fptr.close()

Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import deque, defaultdict


def bfs(graph, start_node, visited):
    size = 0
    queue = deque()
    visited.add(start_node)
    queue.append(start_node)
    while len(queue) > 0:
        current_node = queue.popleft()
        size += 1
        for node in graph[current_node]:
            if node not in visited:
                visited.add(node)
                queue.append(node)
    return size, visited


# Complete the roadsAndLibraries function below.
def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib <= c_road:
        return c_lib * n
    
    # create graph
    graph = defaultdict(set)
    for n1, n2 in cities:
        graph[n1].add(n2)
        graph[n2].add(n1)
    
    allcities = set(range(1, n+1))
    visited = set()
    cost = 0
    for node in graph.keys():
        if node not in visited:
            size, visited = bfs(graph, node, visited)
            cost += (size - 1) * c_road + c_lib

    standalone = allcities - visited
    cost += len(standalone) * c_lib
    return cost


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        nmC_libC_road = input().split()

        n = int(nmC_libC_road[0])

        m = int(nmC_libC_road[1])

        c_lib = int(nmC_libC_road[2])

        c_road = int(nmC_libC_road[3])

        cities = []

        for _ in range(m):
            cities.append(list(map(int, input().rstrip().split())))

        result = roadsAndLibraries(n, c_lib, c_road, cities)

        fptr.write(str(result) + '\n')

    fptr.close()

Solution in cpp

Approach 1.

#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int f(int a){return p[a]==a?a:p[a]=f(p[a]);}
void u(int a, int b){p[f(a)] = f(b);}
signed main()
{
    int T;cin >> T;while(T--){
        int N, M, a, b;
        long long c, d;
        cin >> N >> M >> c >> d;
        p.clear();p.resize(N);
        iota(p.begin(), p.end(), 0);
        while(M--){
            cin >> a >> b;
            --a, --b;
            u(a, b);
        }
        int comp=0;
        for(int i=0;i<N;++i){
            if(p[i]==i)++comp;
        }
        cout << (comp*c+(N-comp)*min(c, d)) << "\n";
    }

    return 0;
}

Approach 2.

#include <bits/stdc++.h>

using namespace std;
void dfs(vector<int> v[], bool arr[], int s){
    arr[s] = true;
    for(int i = 0; i <v[s].size(); i++){
        if(arr[v[s][i]] == false){
            dfs(v,arr,v[s][i]);
        }
    }
}
int main() {
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int n;
        int m;
        long x;
        long y;
        cin >> n >> m >> x >> y;
        vector<int> v[n];
        bool arr[n];
        for(int a1 = 0; a1 < m; a1++){
            int city_1;
            int city_2;
            cin >> city_1 >> city_2;
            v[city_1-1].push_back(city_2-1);
            v[city_2-1].push_back(city_1-1);
        }
        for(int i = 0; i<n; i++){
            arr[i] = false;
        }
        int j = 0;
        for(int i = 0; i<n; i++){
            if(arr[i] == false){
                dfs(v,arr,i);
                j++;
            }
        }
        long long int ans = j * x;
        ans += ((x < y) ? x : y)*(n-j);
        cout<<ans<<endl;
    }
    return 0;
}

Approach 3.

#include <bits/stdc++.h>

using namespace std;

long long dfs(vector<int> &visited,list<int> *adj,int s)
{
    visited[s]=1;
    list<int> ::iterator it;
    long long sum=1;
    for(it=adj[s].begin();it!=adj[s].end();it++)
    {
        if(visited[*it]==0)
            sum+=dfs(visited,adj,*it);
    }
    return sum;
}

int main() {
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int n;
        int m;
        long x;
        long y;
        long long sum=0;
        cin >> n >> m >> x >> y;
        list<int> *adj=new list<int>[n];
        for(int a1 = 0; a1 < m; a1++){
            int city_1;
            int city_2;
            cin >> city_1 >> city_2;
            adj[city_1-1].push_back(city_2-1);
            adj[city_2-1].push_back(city_1-1);
        }
        
        vector<int> visited(n,0);
        for(int i=0;i<n;i++)
        {
            if(visited[i]==0)
            {
                int n=dfs(visited,adj,i);
                sum+= (long long)x+(long long)((n-1)*(min(x,y)));
            }
                
        }
        cout<<sum<<endl;
    }
    return 0;
}