You are viewing a single comment's thread. Return to all comments →
JAVA 8
public static long roadsAndLibraries(int vertices, int c_lib, int c_road, List> cities) { //base case if(c_lib
//arraylist for adjacency list ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); for(int i = 0;i<vertices;i++) { arr.add(new ArrayList<Integer>()); } //adding edges --> adjacency list for(int i = 0;i<cities.size();i++) { arr.get(cities.get(i).get(0)-1).add(cities.get(i).get(1)-1); arr.get(cities.get(i).get(1)-1).add(cities.get(i).get(0)-1); } boolean[] visited = new boolean[vertices]; long cost = (long)vertices*c_lib; long road = 0; for(int i = 0;i<vertices;i++) { if(!visited[i]) { road += connectedRoads(i,arr,visited); long tempc = ((long)vertices - road)*(long)c_lib + road*(long)c_road; cost = Math.min(cost, tempc); } } return cost; } private static long connectedRoads(int source,ArrayList<ArrayList<Integer>> arr, boolean[] visited) { long roads = 0; visited[source] = true; //using bfs Queue<Integer> q = new LinkedList(); q.offer(source); while(!q.isEmpty()) { int current = q.poll(); for(int next : arr.get(current)) { if(visited[next]!= true) { visited[next]=true; roads++; q.add(next); } } } return roads; }
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
JAVA 8
public static long roadsAndLibraries(int vertices, int c_lib, int c_road, List> cities) { //base case if(c_lib