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;
}

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;
}

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

https://medium.com/p/3b035eb9e9f1

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;
}

}`