We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Roads and Libraries
Roads and Libraries
+ 0 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; }
+ 0 comments C++ Solution DFS FUNC
long dfs(map<int,vector<int>> &paths, vector<bool> &visited, int current){ // initialize node count to 1 int node_count = 1; // set this current position in the visited array to true visited[current] = true; // iterate through the paths and dfs all non visited nodes/integers for(auto it = paths[current].begin();it!=paths[current].end();it++){ if(!visited[*it]){ // add the return value of dfs to the node count node_count += dfs(paths,visited,*it); } } return node_count; }
roadsAndLibraries FUNC
long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) { // initialize answer long long answer = 0; long long extra_costs = 0; long long total_components = 0; // rename constants int cost_library = c_lib; int cost_road = c_road; int number_cities = n; int paths_given = cities.size(); // build our adjacency map, bidirectional map<int,vector<int>> paths; for(int i=0;i<cities.size();i++){ int x = cities[i][0]; int y = cities[i][1]; paths[x].push_back(y); paths[y].push_back(x); } // build our visited vector, initialize to false vector<bool> visited(n,false); // iterate over the adjacency map and for(auto it=paths.begin();it!=paths.end();it++){ if(!visited[it->first]){ int component_size = dfs(paths,visited,it->first); total_components += component_size; answer += min((((component_size-1)*(cost_road))+(cost_library)),((component_size)*(cost_library))); } } if(n>total_components){ extra_costs = (n-total_components)*cost_library; } return answer+extra_costs; }
+ 0 comments the solution involves build the graph and then find the connected components the mininum edges to connect all the nodes in a graph is the total of nodes - 1 the cost of the roads is the number of edges - 1 * cost of the road And for each graph component we need to add a library
def dfs(visited, graph, node): if node not in visited: visited.add(node) for neighbour in graph[node]: dfs(visited, graph, neighbour) return visited def roadsAndLibraries(n, c_lib, c_road, cities): if c_lib <= c_road: return c_lib * n # build the graph graph = {} for i in range(1, n + 1): graph[i] = [] for city in cities: graph[city[0]].append(city[1]) graph[city[1]].append(city[0]) # split graphs into components graph_components = set() for node in range(1, n + 1): graph_elements = dfs(set(), graph, node) if graph_elements not in graph_components: graph_components.add(frozenset(graph_elements)) print(f"graph_components: {graph_components}") # calculate the cost cost_road = 0 lib_cost = 0 for i in graph_components: cost_road += c_road * (len(i) - 1) lib_cost += c_lib print(f"cost_road: {cost_road}, lib_cost: {lib_cost}") return cost_road + lib_cost
+ 0 comments
+ 1 comment Some of my test cases are failing due to Wrong Answer. Could anyone please let me know where I am going wrong
`
static Integer findParent(int node, List parent){ if(node == parent.get(node)){ return node; }
return parent.set(parent.get(node), findParent(parent.get(node), parent)); } static void union(int u, int v, List<Integer> parent, List<Integer> rank){ int pu = findParent(u, parent); int pv = findParent(v, parent); if(rank.get(pu) > rank.get(pv)) { parent.set(pv, pu); }else if(rank.get(pu) < rank.get(pv)) { parent.set(pu, pv); }else { parent.set(pv, pu); rank.set(pu, rank.get(pu) + 1); } } public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) { List<Integer> parent = new ArrayList<>(); List<Integer> rank = new ArrayList<>(); HashMap<Integer, Integer> freqMap = new HashMap<>(); long result = 0; for(int i = 0; i <= n; i++){ parent.add(i); rank.add(0); } for(int i = 0; i< cities.size(); i++){ int u = cities.get(i).get(0); int v = cities.get(i).get(1); union(u, v, parent, rank); } for(int i = 1; i <= n; i++){ Integer fp = findParent(i, parent); freqMap.put(fp, freqMap.getOrDefault(fp, 0) + 1); } for(Integer val: freqMap.values()){ result += Math.min((long)val * c_lib, ((long)(val - 1) * c_road) + c_lib); } return result; }
}`
Load more conversations
Sort 833 Discussions, By:
Please Login in order to post a comment