Salve, sto imparando a implementare codici per i grafi ed in particolare avevo provato a fare super marco 2 come problema e riesco a risolvere tutto fuorché tre task in cui sforo il tempo (di conseguenza il punteggio è 10/100 nonostante risolva tutti meno 3 i task)
Dove posso risparmiare tempo?
Ti do qualche consiglio:
- Se ti serve una struttura dove poter inserire ed eliminare il primo e l’ultimo elemento in tempo costante ti consiglio la
dequedell’stl.
2 Evita di inserire nella coda nodi che hai già visitato, quindi fai il controllo ed aggiorni direttamente prima di inserirlo.
3 Non serve scorrere il vector con quella sintassi un po’ bruttina.
Fabio.
3 Mi Piace
Se vogliamo essere corretti la pila( std::stack) è una strutta lifo, quindi l’ ulitmo elemento a essere inserito è il primo ad uscire.
Se vuoi simulare una pila con il vector dovresti aggiungere e rimuovere dalla fine e non dal suo inizio.
La funzione erase elimina un elemento in tempo lineare al numero di elementi presenti nel vector O(N).
Dovendo simulare la pila ti conviene usufruire delle funzioni std::vector::pop_back e std::vector::back che operano in tempo costante O(1).
Utilizzando queste due funzioni e cambiando le righe :
corrente=pila[0];
pila.erase(pila.begin());
in:
corrente= pila.back();
pila.pop_back();
La soluzione ottiene 100.
Se vuoi migliorare con i grafi ti consiglio di riscirvere la soluzione utilizzando le due visite dfs(ricorsiva) e bfs (coda) “correttamente”.
Come nello scorso post ti invito a usare i for each, sono molto comodi da usare.
Per i vettori di grandi dimensioni è consigliabile dichiararli in globale.
1 Mi Piace
Ciao, innanzitutto grazie per la risposta esplicativa però non capisco cosa intendi con riscrivere correttamente le due visite: a parte, il fatto che cancellavo l’elemento iniziale e non quello finale, il codice non sarebbe una visita corretta?
Poi, scusa ma non ricordo cosa intendi con for each
Mi chiedo anche se ci sia un modo per eliminare l’elemento iniziale in tempo O(1)
Ciao, come mi consigli di scorrere il vettore?
E onestamente non capisco perché debba per forza partire dall’elemento in fondo del vettore pila e del perché non possa fare il contrario
E un’altra cosa ancora(scusa se ti sommergo di domande): cambia qualcosa se accedo all’ultimo elemento con un v[v.size()-1] o con un v.back()?
La visita sarebbe stata corretta ma non avrebbe rispecchiatto il concetto di pila.
Puoi anche fare il contrario ma in quel caso non si parla più di pila ma di coda.
Per:
Intendo questo :
// per ogni elemento presente in v[corrente]
for(int i : v[corrente]){
pila.push_back(i);
}
Molto più semplice e sbrigativo di utilizzare gli iteratori.
Usando v.back() ti restituisce una copia del ulitmo elemento, mentre con v[v.size() - 1] fai riferimento all’ ulitma posizione del vettore e puoi anche cambiare il cotenuto.
Intendo di utilizzare una coda (std::queue) per effettuare la bfs e utilizzare una funzione ricorisva per effettuare la dfs.
Con il vector non puoi ma con una std::deque si, tramite la funzione std::deque::pop_front come suggerito da @frakkiobello
1 Mi Piace
Non ho ben capito se devo usare una coda o una deque
E la visita dfs va necessariamente implementata con la ricorsione?
Dipende, diciamo che se non ti serve l’ accesso ad ogni elemento presente nella struttura dati è preferibile la coda altrimenti la deque.
Sto insistendo un po’ sul concetto di coda e di pila perché a seconda della struttura che usi cambia come visiti il grafo.
Se usi uno stack-pila effettui una ricerca in profondità.
Se usi una queue-coda effettui una ricerca per ampiezza.
No, non è neccessario.
1 Mi Piace
Ok, grazie, ma se la deque mi permette sia di eliminare il primo che ultimo elemento in tempo costante a cosa mi serve imparare ad usare anche la queue o la pila?
Bella domanda, non saprei come risponderti 
Probabilmente coda e pila sono più veloci nelle operazioni ma non ne sono sicuro 
Conoscere il funzionamento di una pila o coda sono nozioni basiche, quindi volendo o no è sempre meglio saperlo.
1 Mi Piace
Grazie mille, mi hai dato un sacco di consigli utilissimi!
1 Mi Piace