• + 0 comments

    C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )

    long roadsAndLibraries(
        int const & citiesCount,
        int const & costLib, 
        int const & costRoad,
        std::vector<std::vector<int>> const & roads
    ){
        using namespace std;
        if(costLib <= costRoad){
            return static_cast<long>(citiesCount) * costLib;
        }
        auto citiesConnected{unordered_map<int, vector<int>>{}};
        for(auto const & road: roads){
            citiesConnected[road.at(0)].emplace_back(road.at(1)); 
            citiesConnected[road.at(1)].emplace_back(road.at(0)); 
        }
        auto citiesVisited{vector<bool>(citiesCount, false)};
        auto isolatedRegions{0};
        auto doBFS = [&](auto const & city){
            auto qBFS{queue<int>{}};
            qBFS.push(city);
            citiesVisited.at(city - 1) = true;
            while(!qBFS.empty()){
                for(auto const & neighbour: citiesConnected.at(qBFS.front())){
                    if(citiesVisited.at(neighbour - 1)){
                       continue; 
                    }
                    qBFS.push(neighbour);
                    citiesVisited.at(neighbour - 1) = true;
                }
                qBFS.pop();
            }
        };
        for(auto const & [city, _]: citiesConnected){
            if(citiesVisited.at(city - 1)){
                continue;
            }
            doBFS(city);
            ++isolatedRegions;
        }
        isolatedRegions += citiesCount - citiesConnected.size();
        return isolatedRegions * static_cast<long>(costLib) +
            (citiesCount - isolatedRegions) * static_cast<long>(costRoad);
    }