PROBLEMA Roads and Libraries

[Marcus Aseth]

Stavo cercando di risolvere questo "puzzle" su hackerrank.com chiamato Roads and Libraries e la mia soluzione è il codice sotto.
Il codice passa con successo i primi 3 "test case", però fallisce gli altri perchè impiega troppo tempo ad eseguire.
Per spiegare il mio ragionamento (che però è uno spoiler al problema, quindi magari prima provate a risolverlo da voi e non leggete oltre :) )

Spoiler

Ci sono solo 2 soluzioni possibili, la prima è che una sola città ha una libreria e tutte le altre sono connesse da strade, il secondo caso è che tutte le città hanno la propria libreria.
Questo ragionamento però si applica a "clusters" di città, perchè ci possono essere piccoli gruppi di città isolate dalle altre.
Percui il mio algoritmo prima di tutto costruisce una mappa di questi "clusters" di città, e poi applica la formula sopra in base al numero di clusters.

Il mio problema dunque penso stia nel codice che organizza le città in clusters, semplicemente impiega troppo tempo.
C'è un modo più efficiente/veloce per individuare il numero di clusters di città?
Attenzione, non chiedo la risposta per poter passare il problema, chiedo perchè altrimenti ho perso tempo a cercare di risolverlo e non ho imparato nulla di nuovo :|

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class City {
public:
    City(long id) :ID{ id } {}
public:
    long ID;
    vector<long> connectedID;
};


int main()
{
    long queryN;
    cin >> queryN;

    long cityN, roadN, libCost, roadCost;
    for (size_t i = 0; i < queryN; i++)
    {
        cin >> cityN >> roadN >> libCost >> roadCost;

        vector<City> Cities;
        //make Cities
        for (size_t i = 0; i < cityN; i++) {
            Cities.push_back(City(i));
        }

        //make Roads
        for (size_t i = 0; i < roadN; i++) {
            long from, to;
            cin >> from >> to;
            from--, to--;
            Cities[from].connectedID.push_back(to);
            Cities[to].connectedID.push_back(from);
        }

        //organize cities by connected clusters
        vector<vector<City*>> Clusters;
        vector<bool> sorted(cityN);

        for (size_t currCity = 0; currCity < cityN; currCity++)
        {
            if (!sorted[currCity])
            {
                for (auto& vecC : Clusters) {
                    if (sorted[currCity]) { break; }
                    for (auto& city : vecC) {
                        if (sorted[currCity]) { break; }
                        for (auto& connection : city->connectedID) {

                            if (connection == currCity)
                            {
                                vecC.push_back(&Cities[currCity]);
                                sorted[currCity] = true;
                                break;
                            }
                        }
                    }
                }
                //still not sorted, means it is not connected to an existing cluster
                if (!sorted[currCity])
                {
                    Clusters.push_back(vector<City*>(1, &Cities[currCity]));
                    sorted[currCity] = true;
                }
            }
        }

        //calculate expenses
        long totalCost{};
        //minimum 1 library per cluster of cities
        totalCost += libCost*Clusters.size();
        //other cities
        totalCost += libCost < roadCost ? libCost*(cityN - Clusters.size()) : roadCost*(cityN - Clusters.size());

        cout << totalCost << endl;

    }

    return 0;
}

 

[Marcus Aseth]

Ho anche provato diversamente, questa volta passo 4 test case ma gli altri di nuovo falliscono perchè l'algoritmo richiede troppo tempo :|

#include <iostream>
#include <map>
#include <list>
using namespace std;

struct Pair {
    Pair(long f, long t) :from{ f }, to{ t } {}
    long from, to;
};

int main()
{
    long queryN;
    cin >> queryN;

    long cityN, roadN, libCost, roadCost;
    for (size_t i = 0; i < queryN; i++)
    {
        cin >> cityN >> roadN >> libCost >> roadCost;

        map<int, bool> Cities;
        //make Cities
        for (size_t i = 0; i < cityN; i++) {
            Cities[i] = false;
        }

        list<Pair> connections;
        //make Roads
        for (size_t i = 0; i < roadN; i++) {
            long from, to;
            cin >> from >> to;
            connections.push_back(Pair(--from, --to));
        }

        long totalCost{};
        long newLib{};
        long sortedOut{};
        long unsorted = cityN;

        bool jobWasDone = false;
        while (connections.size() > 0)
        {
            // try and make a new library
            if (!jobWasDone)
            {
                for (auto& city : Cities)
                {
                    if (city.second == false) {
                        newLib++;
                        city.second = true;
                        break;
                    }
                }
            }

            jobWasDone = false;
            for (auto connection = connections.begin(); connection != connections.end();)
            {
                if (Cities[connection->from] == false && Cities[connection->to] == false) {
                    connection++;
                    continue;
                }
                else if (Cities[connection->from] == true && Cities[connection->to] == true) {
                    connection = connections.erase(connection);
                    continue;
                }
                else
                {
                    sortedOut++;
                    Cities[connection->from] = Cities[connection->to] = true;
                    connection = connections.erase(connection);
                    jobWasDone = true;
                }
            }
        }

        long isolatedCities = cityN - sortedOut - newLib;
        totalCost += (isolatedCities * libCost) + (newLib * libCost);
        totalCost += libCost < roadCost ? libCost*sortedOut : roadCost*sortedOut;

        cout << totalCost << endl;

    }
    return 0;
}

 

[Marcus Aseth]

Come non detto, ho insistito un pò tirando contro a questo problema un pò di tutto a random, ed alla fine l'ho risolto con questa versione che usa una funzione ricorsiva :D
Se avete soluzioni più efficienti comunque sono curioso di sentirle
ps:ignorate i "long" messi a random, stavo facendo prove nel caso il data set fosse troppo grande, ma non si è rivelato essere un problema.

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct City {
    City() :visited{ false } {}

    bool visited;
    vector<City*> connections;
};

long measureCluster(City* city);

int main()
{
    long queryN;
    cin >> queryN;

    long cityN, roadN, libCost, roadCost;
    for (size_t i = 0; i < queryN; i++)
    {
        cin >> cityN >> roadN >> libCost >> roadCost;

        //make Cities
        map<int, City> Cities;

        //make Roads
        long from, to;
        for (size_t i = 0; i < roadN; i++) {
            cin >> from >> to;
            from--, to--;

            Cities[from].connections.push_back(&Cities[to]);
            Cities[to].connections.push_back(&Cities[from]);
        }

        //data
        long newLib{};
        long unsolvedCities{};
     
        //measure clusters
        for (auto& city : Cities)
        {
            long resoult = measureCluster(&city.second);
            if (resoult > 0)
            {
                newLib++;
                unsolvedCities += resoult - 1;
            }
        }

        //calculate expense
        long totalCost{};
        long isolatedCities = cityN - Cities.size();

        totalCost += (isolatedCities + newLib) * libCost;
        totalCost += libCost < roadCost ? libCost*unsolvedCities : roadCost*unsolvedCities;
        cout << totalCost << endl;
    }
    return 0;
}

long measureCluster(City* city)
{
    if (!city->visited)
    {
        city->visited = true;
        int visitedCount{ 1 };

        for (auto& connection : city->connections)
        {
            visitedCount += measureCluster(connection);
        }
        return visitedCount;
    }

    return 0;
}