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

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