Aiuto per police2

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

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

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

( 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   

Grazie ancora, ci provero’ :slight_smile: