Aiuto per police2

Aiuto
1

Non riesco proprio a fare piu’ di 30 punti su police2, c’e’ qualche ottimizzazione che mi sfugge?
Mi vanno fuori tempo i subtask 3, 4 e 6.
Per ora il codice che uso e’ il seguente:

#include <fstream>
#include <vector>
#include <stack>
#include <utility>
using namespace std;

class Grafo {
    private:
        vector<size_t> adj;

    public:
        Grafo(const size_t& n) {
            this->adj.resize(n);
        }

        void add_edge(const size_t& u, const size_t& v) {
            this->adj[u] = v;
        }

        pair<size_t, size_t> dfs(const size_t& s) {
            vector<bool> visited(this->adj.size(), false);

            stack<size_t> st;
            st.push(s);

            vector<size_t> dist(this->adj.size(), -1);
            dist[s] = 1;

            size_t next_to_visit = s + 1;
            while(!st.empty()) {
                size_t current_node = st.top();
                st.pop();

                if(current_node == next_to_visit + 1) next_to_visit = current_node;

                visited[current_node] = true;

                size_t next_node = this->adj[current_node];

                if(visited[next_node]) return {dist[current_node] - dist[next_node] + 1, next_to_visit};

                st.push(next_node);
                dist[next_node] = dist[current_node] + 1;
            }

            return {0, s + 1};
        }
};

int main(int argc, char** argv) {
    ifstream in("input.txt");
    ofstream out("output.txt");

    size_t N;
    in >> N;

    Grafo grafo(N);
    for(size_t i = 0; i < N; i++) {
        size_t tmp;
        in >> tmp;

        grafo.add_edge(i, tmp);
    }

    size_t max_cycle = 0;
    for(size_t i = 0; i < N; i++) {
        auto [cycle_length, next_to_visit] = grafo.dfs(i);
        max_cycle = max(max_cycle, cycle_length);

        i = next_to_visit;
    }

    out << max_cycle << endl;
}
2

Il problema è che facendo partire una dfs per ogni nodo ottieni un algoritmo O(N^2) che quindi non paassa i testcase grandi.
Prova a capire come potresti esplorare il grafo in un solo passaggio riuscendo a trovare i cicli e anche riuscire a capire se stai entrando in un nuovo ciclo mai esplorato o uno esplorato in precedenza (per non contare i cicli già contati più volte).

1 Mi Piace
3

Ciao! Inanzitutto grazie per la risposta, avevo provato il seguente codice per evitare di ripartire da un nodo gia’ visitato ma va comunque fuori tempo, dovrei usare il graph coloring?

#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

set<size_t> nodes;

class Grafo {
    private:
        vector<size_t> adj;
    public:
        Grafo(const size_t& n) {
            this->adj = vector<size_t>(n, -1);
        }

        void add_edge(const size_t& u, const size_t& v) {
            this->adj[u] = v;
        }

        size_t dfs(const size_t& s) {
            vector<bool> visited(this->adj.size(), false);

            stack<size_t> st;
            st.push(s);

            vector<size_t> dist(this->adj.size(), -1);
            dist[s] = 1;

            while(!st.empty()) {
                size_t current_node = st.top();
                st.pop();

                visited[current_node] = true;
                nodes.erase(current_node);

                size_t next_node = this->adj[current_node];

                if(visited[next_node]) return dist[current_node] - dist[next_node] + 1;

                st.push(next_node);
                dist[next_node] = dist[current_node] + 1;
            }

            return 0;
        }
};

int main(int argc, char** argv) {
    ifstream in("input.txt");
    ofstream out("output.txt");

    size_t N;
    in >> N;

    size_t max_cycle = 0;

    Grafo grafo(N);
    for(size_t i = 0; i < N; i++) {
        size_t tmp;
        in >> tmp;

        if(i == tmp) max_cycle = 1;
        else nodes.insert(tmp);

        grafo.add_edge(i, tmp);
    }


    while(!nodes.empty()) {
        size_t current_node = *nodes.begin();
        nodes.erase(current_node);

        size_t cycle = grafo.dfs(current_node);
        if(cycle > max_cycle) max_cycle = cycle;
    }

    out << max_cycle << endl;
}
5

( ho fatto un casino col messaggio di prima sorry :frowning: )
sì esatto il concetto è salvarsi per ogni nodo a quale percorso appartiene, e anche in che posizione sei nel percorso attuale, per calcolarti la lunghezza dell’eventuale ciclo.

io l’ho pensata così:

numero_percorso = 0
posizione_percorso = 0
per ogni nodo n (indice i):
    se n è già visitato:
        salta
    numero_percorso += 1
    partenza = i
    arrivo = i

    // seguo il percorso finchè non finisce o entro in un ciclo
    loop infinito:
        se arrivo non è visitato:
            segna arrivo come visitato
            salva numero_percorso e posizione_percorso per il nodo arrivo
            partenza = arrivo
            arrivo = prossimo nodo // esempio arrivo=g[arrivo];
        se l'arrivo è visitato e numero_percorso è uguale a quello dell'arrivo: // entro in un loop nuovo
            lunghezza_ciclo = posizione_percorso(partenza)-posizione_percorso(arrivo)+1
            salva la lunghezza massima
            esci dal loop infinito
        se l'arrivo è visitato ma numero_percorso è diverso: //sono entrato in un loop già contato
            esci dal loop infinito
        posizione_percorso += 1
1 Mi Piace
6

Grazie ancora, ci provero’ :slight_smile: