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