[HackerRank] Roads and Libraries

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:

The cost of repairing any road is  dollars, and the cost to build a library in any city is  dollars.

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.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following format:

• The first line contains four space-separated integers describing the respective values of  (the number of cities),  (the number of roads),  (the cost to build a library), and  (the cost to repair a road).
• Each line  of the  subsequent lines contains two space-separated integers,  and , describing a bidirectional road connecting cities  and .

Constraints

• Each road connects two distinct cities.

Output Format

For each query, print an integer denoting the minimum cost of making libraries accessible to all the citizens on a new line.

Sample Input

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

4
12

Explanation

We perform the following  queries:

1. HackerLand contains  cities 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 .
   • Repair the road between cities  and  at a cost of .
   • Repair the road between cities  and  at a cost of .
   This gives us a total cost of . Note that we don't need to repair the road between cities  and  because we repaired the roads connecting them to city !
2. In this scenario it's optimal to build a library in each city because the cost of building a library () is less than the cost of repairing a road ().
   There are  cities, so the total cost is .

Thought process:

Essentially, every connected component needs at least one library. For every connected component, let count be the number of nodes in the component. There can be two cases:

• If c_road < c_lib, then the minimum cost is to build one library and count - 1 roads to connect the cities.
• If c_road > c_lib, then the minimum cost is to build one library for each city.

If c_road = c_lib, then two ways yield the same result so it doesn't matter.

So the idea is to use DFS to count the number of nodes for each connected components, and then calculate the minimum cost.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

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

Time complexity:

For each query, say v is the number of nodes and e the number of edges. DFS's time complexity is O(v + e). There are q queries, so the overall complexity is O(q(v + e)).