Appetito aracnide 40/100

ho provato a risolvere questo esercizio, ma ho preso solo 40/100 tuttavia sia nei casi d’esempio che in quelli che mi sono inventato l’output è corretto, praticamente nella coda tengo presente il percorso fino a quel momento + lo stato (true=slurp false=bleah) faccio una visita in ampiezza e passo su un nodo solo se non ci sono già passato con lo stesso stato, questo è il codice:

#include <bits/stdc++.h>

using namespace std;

struct tre{
    int next;
    string percorso;
    bool stato;
};

int main() {
    ifstream in("input.txt");
    ofstream out("output.txt");
    typedef vector<int>::iterator it;
    int N,M;
    in>>N>>M;
    queue<tre> coda;
    bool visiteds[N]={};    //true
    bool visitedb[N]={};    //false
    vector<int> nodi[N];
    string final;
    for(int i=0;i<M;i++){
        int a,b;
        in>>a>>b;
        nodi[a].push_back(b);
        nodi[b].push_back(a);
    }
    coda.push({0,"0 ",false});
    visitedb[0]=true;
    while(!coda.empty()){
        int cur=coda.front().next;
        string percorsoc=coda.front().percorso;
        bool stato=!coda.front().stato;
        if(cur==0&&!stato){
            final=percorsoc;
            break;
        }
        coda.pop();
        for(it it=nodi[cur].begin();it!=nodi[cur].end();++it){
            string percorso=percorsoc;
            int next=(*it);
            if(stato){
                if(!visiteds[next]){
                    visiteds[next]=true;
                    percorso.append(to_string(next)+" ");
                    coda.push({next,percorso,stato});
                }
            }
            else if(!visitedb[next]){
                visitedb[next]=true;
                percorso.append(to_string(next)+" ");
                coda.push({next,percorso,stato});
            }
        }
    }
    out<<final.size()/2-1<<endl<<final;
    return 0;
}

Hai tenuto presente percorsi tipo cappio:
ad esempio 0-3-4-7-8-11-7-4-3-1: avanti da 1 a 7, ciclo dispari 7-8-11-7 indietro da 7 a 0.

1 Mi Piace

mi sembrerebbe di si, per esempio con questo input:
6 6
0 1
1 2
2 3
3 4
4 5
5 3
il risultato è
9
0 1 2 3 4 5 3 2 1 0
che è corretto.

prova con questo input:
11 11
0 10
1 10
1 7
4 7
4 8
6 8
3 6
3 5
9 5
2 9
9 7

1 Mi Piace

Grazie mille, non capisco il motivo per cui ho usato una stringa e non un vettore per memorizzare il percorso, pessima idea ahah.