In order to learn java, I have been working through some HackerRank problems. The one I am asking about is here:
- There are cities that we can connect together by repairing some destroyed roads, provided by integer pairs
- We can build a library in one or more cities
- There is a cost to the roads and a different cost to the libraries
- All cities must be part of a group that contains a library, i.e. you can get there by a repaired road -we are trying to minimize cost
I am certain that my code works, through testing on Hackerrank, however I am not certain I don't have conventions wrong, poor variable names, poor commenting, using Long instead of long or Integer instead of int etc. Do you see any opportunities for improvement ?
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
/** This is a solution to
* https://www.hackerrank.com/challenges/torque-and-development/problem
* class must be name Solution to run on Hackerrank
*/
public class Solution {
private static List<List<Integer>> adjCities;
private static boolean[] visited;
// do a dfs to find every city that can be connected to any given group of cities
private static void dfs(int city){
visited[city] = true;
for (int c=0; c< adjCities.get(city).size(); c++){
if(!visited[ adjCities.get(city).get(c)]) {
dfs( adjCities.get(city).get(c) );
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//Scanner in = new Scanner(new File("test_4.txt")); // sample input file
int queries = in.nextInt();
// loop through each of the blocks which represent separate problems
for(int cntQueries = 0; cntQueries < queries; cntQueries++){
int numCities = in.nextInt();
int numRoads = in.nextInt();
long costLibrary = in.nextLong(); // these must be long, not int to avoid
long costRoad = in.nextLong(); // overflow in the totalCost
long totalCost; // totalCost must also be long, not int
// make the adjacency list as a list of null length lists
adjCities= new ArrayList<>();
for (int c = 0; c <= numCities; c++) {
adjCities.add(new ArrayList<>());
}
// read in the data on the connecting roads. add each road to the adjacency list
// for both cities
int city1;
int city2;
for(int cntRoads = 0; cntRoads < numRoads; cntRoads++){
city1 = in.nextInt();
city2 = in.nextInt();
adjCities.get( city1).add(city2); // add to the adjacency list
adjCities.get( city2).add(city1);
}
if(costLibrary <= costRoad){
// if the cost of building a library is less than the cost of repairing a road
// we just build a library in every city, without repairing any roads
totalCost = (long) (costLibrary * numCities);
}
else{
// if the cost of repairing a road is less than building a library,
// we need to do a search to see how many cities can be connected. i.e.
// we want the fewest number of groups possible.
// Each group gets a single library. Count the number of libraries made
// do a depth first search on our cities, to see which cities can be grouped together
int librariesBuilt=0;
visited = new boolean[numCities+1];
for (int c=1; c <= numCities; c++){
if(!visited[c]) {
dfs(c);
librariesBuilt++;
}
}
// the total number of roads build plus the number of libraries built will always equal
// the number of cities. Therefore the number of roads built will always be the number
// of cities less the number of libraries built
totalCost = librariesBuilt * costLibrary + (numCities-librariesBuilt) * costRoad;
}
//System.out.println("The total cost is ");
System.out.println(totalCost);
}
}
}