• + 0 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; }

    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).