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.
Description
This function calculates the minimum cost to provide library access to all citizens of HackerLand. It takes as input the number of cities, the cost of building a library, the cost of repairing a road, and a list of bidirectional roads that can be built between cities.
The function employs the Disjoint Set Union (DSU) data structure to determine connected components in the graph of cities and roads. It then calculates the cost needed to ensure that every citizen can access a library, either directly in their city or through roads to other cities containing libraries.
Parameters
n (int): The number of cities in HackerLand.
c_lib (int): The cost to build a library.
c_road (int): The cost to repair a road.
cities (vector>): A list of bidirectional roads that can be built between cities.
Return
long: The minimal cost required to provide library access to all citizens.
Algorithm Explanation
If the cost of building a library (c_lib) is less than or equal to the cost of repairing a road (c_road), then it's optimal to build a library in each city. The total cost would be n * c_lib.
Otherwise, the algorithm uses a Disjoint Set Union (DSU) data structure to find the connected components in the graph.
For each road in the cities list, the DSU is updated to indicate that the two cities are connected.
After processing all roads, the algorithm calculates the number of libraries required for each connected component.
The total cost is calculated by summing the following for each connected component:
(component_libs[root] - 1) * c_road: The number of roads needed within the component minus one (to avoid double counting) multiplied by the cost of repairing a road.
c_lib: The cost of building a library in the root city of the component.
The final result is the sum of the calculated costs.
**Code **
class DisjointSet{
vector parent;
vector rank;
public:
DisjointSet(int n){
parent.resize(n+1);
rank.resize(n+1,0);
for(int i = 1; i <= n; i++)
parent[i] = i;
}
int findPar(int node){
if(parent[node] == node) return node;
return parent[node] = findPar(parent[node]);
}
void unionByRank(int u, int v){
int parent_u = findPar(u);
int parent_v = findPar(v);
if(parent_u == parent_v) return;
if(rank[parent_u] < rank[parent_v])
parent[parent_u] = parent_v;
else if(rank[parent_v] < rank[parent_u])
parent[parent_v] = parent_u;
else{
parent[parent_v] = parent_u;
rank[parent_u]++;
}
}
};
long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) {
if (c_lib <= c_road) {
return n * 1ll * c_lib;
}
DisjointSet ds(n + 1);
for (auto city : cities) {
ds.unionByRank(city[0], city[1]);
}
unordered_map<int, int> component_libs;
for (int i = 1; i <= n; i++) {
int root = ds.findPar(i);
component_libs[root]++;
}
long cost = 0;
for (const auto &pair : component_libs) {
cost += (pair.second - 1) * 1ll * c_road + c_lib;
}
return cost;
}
Time Complexity
Initializing the DSU takes O(n) time, where n is the number of cities.
Processing the roads takes O(m * α(n)) time, where m is the number of roads and α is the inverse Ackermann function (a very slow-growing function, practically considered constant).
Calculating the number of libraries and calculating the total cost both take O(n) time.
Thus, the overall time complexity of the algorithm is O(n + m * α(n)).
Space Complexity
The DSU requires O(n) space for the parent and rank arrays.
The unordered map component_libs requires O(n) space.
Thus, the overall space complexity of the algorithm is O(n).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
Description This function calculates the minimum cost to provide library access to all citizens of HackerLand. It takes as input the number of cities, the cost of building a library, the cost of repairing a road, and a list of bidirectional roads that can be built between cities.
The function employs the Disjoint Set Union (DSU) data structure to determine connected components in the graph of cities and roads. It then calculates the cost needed to ensure that every citizen can access a library, either directly in their city or through roads to other cities containing libraries.
Parameters n (int): The number of cities in HackerLand. c_lib (int): The cost to build a library. c_road (int): The cost to repair a road. cities (vector>): A list of bidirectional roads that can be built between cities. Return long: The minimal cost required to provide library access to all citizens. Algorithm Explanation If the cost of building a library (c_lib) is less than or equal to the cost of repairing a road (c_road), then it's optimal to build a library in each city. The total cost would be n * c_lib. Otherwise, the algorithm uses a Disjoint Set Union (DSU) data structure to find the connected components in the graph. For each road in the cities list, the DSU is updated to indicate that the two cities are connected. After processing all roads, the algorithm calculates the number of libraries required for each connected component. The total cost is calculated by summing the following for each connected component: (component_libs[root] - 1) * c_road: The number of roads needed within the component minus one (to avoid double counting) multiplied by the cost of repairing a road. c_lib: The cost of building a library in the root city of the component. The final result is the sum of the calculated costs. **Code ** class DisjointSet{ vector parent; vector rank; public: DisjointSet(int n){ parent.resize(n+1); rank.resize(n+1,0); for(int i = 1; i <= n; i++) parent[i] = i;
} int findPar(int node){ if(parent[node] == node) return node; return parent[node] = findPar(parent[node]); } void unionByRank(int u, int v){ int parent_u = findPar(u); int parent_v = findPar(v); if(parent_u == parent_v) return; if(rank[parent_u] < rank[parent_v]) parent[parent_u] = parent_v; else if(rank[parent_v] < rank[parent_u]) parent[parent_v] = parent_u; else{ parent[parent_v] = parent_u; rank[parent_u]++; } } }; long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) { if (c_lib <= c_road) { return n * 1ll * c_lib; }
} Time Complexity Initializing the DSU takes O(n) time, where n is the number of cities. Processing the roads takes O(m * α(n)) time, where m is the number of roads and α is the inverse Ackermann function (a very slow-growing function, practically considered constant). Calculating the number of libraries and calculating the total cost both take O(n) time. Thus, the overall time complexity of the algorithm is O(n + m * α(n)). Space Complexity The DSU requires O(n) space for the parent and rank arrays. The unordered map component_libs requires O(n) space. Thus, the overall space complexity of the algorithm is O(n).