If you get WA on 6 hidden tests try this:

1ll*n*c_lib instead of n*c_lib*1ll or n*c_lib (same for 1ll * c_lib + (comp-1) * c_road)

I spent quite some time to figure out why my solution didnt pass the 7 heavy input test cases. It turned out that since i tried to convert the edge list to adjacency matrix, the test ran out of memory. So instead of adjacency matrix, i use std::map as adjacency list. map> toAdjList(int n, vector> cities) { map> result = {}; for (const auto &ct : cities) { int a = ct[0]; int b = ct[1]; if (result.find(a) == result.end()) { result[a] = vector(); } result[a].push_back(b); if (result.find(b) == result.end()) { result[b] = vector(); } result[b].push_back(a); }

return result;

}

long roadsAndLibraries(int n, int c_lib, int c_road, vector> cities) { if (n == 0) return 0; if (n == 1) return c_lib;

vector<bool> visited(n + 1, 0);
map<int, vector<int>> adjList = toAdjList(n, cities);

long totalCost = 0;
queue<int> q;
std::cout << "processig " << n << std::endl;    
for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    q.push(i);
    visited[i] = true;
    long nodeCount = 1;
    while (!q.empty()) {
        int currNode = q.front();
        q.pop();
        for (const auto &adjNode : adjList[currNode]) {
            if (!visited[adjNode]) {
                q.push(adjNode);
                visited[adjNode] = true;
                nodeCount++;
            }
        }
    }
    totalCost += std::min(nodeCount * c_lib, c_lib + (nodeCount - 1) * c_road);
}

return totalCost; 

} `

After thinking about it here is my solution in pseudocode then python:

My Intuition: Cities that can be connected by roads make up an island or a sub graph. Each island only needs 1 library + the cost of the roads between the cities. So you can count the number of islands + the number of roads on each island. However the cost of a road can be so high that it's cheaper to build a library in each city. I had to think about this for a bit, I thought it might be some kind of greedy problem so I tried to break it down. I thought about when 1 road cost < 1 lib cost, 1 road cost == 1 lib cost and 1 road cost > 1 lib cost. Turns out if the cost of building a road is >= the cost of building a library, it makes more sense to put a library in each city (I did the math with the 2 cities 1 road case). So at the end of the day you just have to compare building roads + libraries (one each island) or just building libraries in each city. Also another key point is each road is bi-directional so if you build an adjacency list you have to add edges in both directions.

Psuedocode:

    1. Build adjacency list (with bi-directional edges).
    2. For each city:
        if not visited city add 1 library and start a Breadth First Search starting from this city (new island).
    bfs:
        each city visited = 1 new road, skip cities already visited, add each city visited to list of visited cities.
    3. return min(num_cities * lib_cost, cities_and_roads_cost)

# BFS - O(V + E) - Time | O(2 * E) - Space
def get_roads_from_city(graph, city, visited):
    num_roads = 0
    neighbor_q = []
    visited.add(city)
    for neighbor in graph[city]:
        neighbor_q.append(neighbor)
    while len(neighbor_q) > 0:
        node = neighbor_q.pop(0)
        if node not in visited:
            num_roads += 1
            visited.add(node)
            if node in graph:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        neighbor_q.append(neighbor)
    return num_roads, visited


def roadsAndLibraries(n, c_lib, c_road, cities):
    # Write your code here
    if n == 1:
        return c_lib
    
    graph = {}
    # Build Adjacency List
    for city in cities:
        neighbors = graph.get(city[0], [])
        neighbors.append(city[1])
        graph[city[0]] = neighbors
        
        neighbors = graph.get(city[1], [])
        neighbors.append(city[0])
        graph[city[1]] = neighbors
    
    for city in range(1, n + 1):
        if city not in graph:
            graph[city] = []
    
    # BFS
    def libraries_and_roads_cost(graph):
        num_roads = 0
        num_libraries = 0
        visited = set()
        for city in graph.keys():
            if city not in visited:
                roads, visited = get_roads_from_city(graph, city, visited)
                num_roads += roads
                num_libraries += 1
        return num_libraries * c_lib + num_roads * c_road
    
    libs_only = n * c_lib
    libs_roads = libraries_and_roads_cost(graph)
    return min(libs_only, libs_roads)

Greetings! I wonder if anyone could help me figure out why I get failed tests, my approach is simply to count subgraphs, which should be enough to calculate least possible cost. Thanks!

public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
        if(c_lib <= c_road || cities == null || cities.size() == 0)
            return c_lib * n;
        
        List<List<Integer>> adj = new ArrayList<>(n);
        for(int i = 0; i < n; i++){
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < cities.size(); i++){
            int u = cities.get(i).get(0) - 1;
            int v = cities.get(i).get(1) - 1;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        boolean[] visited = new boolean[n];
        long clusters = 0;
        for(int i = 0; i < n; i++){
            if(visited[i]) continue;
            clusters++;
            Queue<Integer> subGraph = new LinkedList<>();
            subGraph.offer(i);
            while(!subGraph.isEmpty()){
                int curr = subGraph.poll();
                if(visited[curr]) continue;
                visited[curr] = true;
                //subGraph.addAll(adj.get(curr));
                for(Integer next : adj.get(curr)) {
                    if(!visited[next]) subGraph.add(next);
                }
            }
        }

        return (long)(clusters * c_lib) + (long)(n - clusters) * c_road;
    }

I will share some intuition i used: - We need to look at every sub graph of the cities such that each sub graph is a (potential) connected component. - For each connected component, you can either buill one library per city and build no roads, or build one libaray and connect the rest of citis with mininum roads. There can be no in between that is optimum. - For n citis, you alway only need n - 1 roads.