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.

my code with python. i dont know it fail in test case 7 how to debug def roadsAndLibraries(n, c_lib, c_road, cities): if c_road > c_lib: return c_lib * n

list_cities = set(range(1, n + 1))
visited_cities = set()
city_groups = []

for city_pair in cities:
    set_cities = set(city_pair)
    visited_cities.update(set_cities)
    merged = False

    for i, group in enumerate(city_groups):
        if group & set_cities:
            city_groups[i] = group | set_cities
            merged = True
            break

    if not merged:
        city_groups.append(set_cities)

total_cost = 0

for group in city_groups:
    total_cost += (len(group) - 1) * c_road + c_lib

unvisited_cities = list_cities.difference(visited_cities)
total_cost += len(unvisited_cities) * c_lib

return total_cost

Branded lanyards can serve as a useful tool while exploring the concept of Roads and Libraries. As both are integral to connectivity, roads symbolize physical infrastructure, while libraries represent hubs of knowledge. Using lanyards, you can keep your IDs, keys, or event passes handy while navigating these essential spaces. Whether for educational trips or professional events, these lanyards are practical and serve as subtle promotional items to showcase your brand.

Guys , its a Basic disjoint set implemtation using krushkal;

The catch is it will pass all except 7 testcase due to typedef ,

we need to change all the int to long long , cause we multiply

So, we need to even change the long long inside main loop also instead of typecasting at result!!