Aiuto stack overflow Interruttori

Aiuto
1

È la prima volta che lavoro con i grafi e sto cercando di risolvere il problema terry “Interruttori” utilizzando la ricerca in ampiezza.
Il mio programma riesce con successo a risolvere 14 casi in pochissimo tempo, solo per poi fermarsi e dare un errore di stack overflow.
Non ho la più vaga idea del perché succeda.

#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <list>
#include <queue>

using namespace std;

struct structNodo {
    int distanza = -1;
    list<int> collegati;
};

void solve(int t) {

    int N, A, B; //N = numero lampadine, A = n interrutori 1, B = n interrutori 2
    cin >> N >> A >> B;

    vector<int> Z(A), X(B), Y(B); //Z = collegamenti 1, X&Y = collegamenti 2

    for (int i = 0; i < A; i++) cin >> Z[i];
    for (int i = 0; i < B; i++) cin >> X[i] >> Y[i];

    int idx; // indice lampadina
    int ans=-1; // numero interruttori

    //partendo da TUTTE le lampadine attaccate ad un interrutore da un solo cavo, trovo la lampadina piu distante in assoluto da quel punto
    //indice lampadina = lampadina piu lontana
    //numero interruttori = distanza dalla partenza
    structNodo nodo[N];
    queue<int> coda;

    //inizio dagli interrutori di tipo 1
    for(int i=0; i<A; i++) { //per ogni interruttore
        nodo[Z[i]].distanza = 1; //setta la distanza al minimo
        coda.push(Z[i]); //lo mette in coda per essere calcolato
    } //i/A

    //creo i collegamenti (interrutori tipo 2)
    for(int i=0; i<B; i++) { //per ogni interrutore
        nodo[X[i]].collegati.push_back(Y[i]); //collego "x" a "y"
        nodo[Y[i]].collegati.push_back(X[i]); //collego "y" a "x"
    } //i/B

    //visita in ampiezza
    do{ //continua-
        int testa = coda.front(); //salvo la testa della coda per evitare ridondanza nell'uso di funzioni

        for(int i : nodo[testa].collegati) { //prende il primo nodo nella coda
            if(nodo[i].distanza <= 0) { //se il nodo collegato non è mai stato visitato
                coda.push(i); //mette il nodo appena visitato in coda per essere espanso
                nodo[i].distanza = nodo[testa].distanza + 1; //aggiorna la distanza del nodo visitato
            }  //if visitato
        } //for each i / nodo[testa].collegati

        if(nodo[testa].distanza > ans) { //se la distanza è più lontana della precedentemente registrata
            idx = testa; //la lampadina più lontana è sempre l'ultima nella coda
            ans = nodo[testa].distanza; //aggiorno il risultato
        } //if risultato migliore

        coda.pop(); //rimuove il nodo appena visitato dalla coda
    } while (!coda.empty()); //-finchè la coda non è vuota

    cout << "Case #" << t << ": " << idx << " " << ans << "\n";
}

È possibile che il problema è il mio IDE?
Ringrazio in anticipo.

2

Qui stai dichiarando un array a lunghezza variabile sullo stack. Oltre a non essere C++ standard, questo occupa un sacco di memoria sullo stack causando probabilmente lo stack overflow. Non c’è davvero nessun motivo per non usare un std::vector in queste situazioni, che, oltre a essere standard, è allocato sull’heap.

Poi mi permetto un paio di osservazioni su cose migliorabili:

Qui non hai davvero motivo di usare una linked list al posto di un vettore, non ti servono operazioni che un vettore non supporti e le linked list hanno molto più overhead e risultano più lente. Qui non è un problema perché le soluzioni possono essere eseguite senza limiti di tempo ma in altri contesti potrebbe risultare un problema.

Questo può (e dovrebbe) essere un normalissimo while.

Infine, per il futuro, allega sempre il tuo codice per intero. Anche se ti sembra che non sia di nessuna utilità allegare il main, risparmia a chi ti aiuta il tempo di andarlo a cercare sulla piattaforma.

2 Mi Piace
3

Ho provato a seguire i tuoi consigli e adesso funziona senza alcun problema, ti ringrazio molto.