You are viewing a single comment's thread. Return to all 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); }
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )