Salve. Sto provando a risolvere tecla, ma il mio codice fa solo 30/100. In due casi stamperebbe filamenti non esistenti, negli altri (sbagliati) genera un signal 9. Sinceramente, anche provando a mano alcuni casi, non capisco dov’è che il codice potrebbe sbagliare. Quello che faccio è far partire una dfs dal nodo 0, e marcare gli archi su cui passo per evitare cicli. Quando trovo un percorso valido, percorro “in catena” all’indietro le variabili dell’array dove memorizzo i precedenti, e le stampo. Allego il mio codice.
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
int n,m;
vector<int> nodi[50];
bool vis[50];
int prec[50];
int edges[50][50];
int arr;
bool flag=true;
void dfs(int k,int passi){
if(!flag)return;
vis[k]=true;
for(int i=0;i<nodi[k].size()&&flag;i++){
if(nodi[k][i]==0&&passi%2==0&&!edges[k][nodi[k][i]]){
arr=k;
flag=false;
return;
}
if(!edges[k][nodi[k][i]]&&flag){
int p=prec[nodi[k][i]];
prec[nodi[k][i]]=k;
edges[k][nodi[k][i]]=1;
edges[nodi[k][i]][k]=1;
dfs(nodi[k][i],passi+1);
if(!flag)return;
edges[k][nodi[k][i]]=0;
edges[nodi[k][i]][k]=0;
prec[nodi[k][i]]=p;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b; cin>>a>>b;
nodi[a].push_back(b);
nodi[b].push_back(a);
}
for(int i=0;i<n;i++){
vis[i]=false;
for(int y=0;y<n;y++)edges[i][y]=false;
}
dfs(0,0);
vector<int> perc;
perc.push_back(0);
while(arr!=0){
perc.push_back(arr);
arr=prec[arr];
}
perc.push_back(0);
reverse(perc.begin(),perc.end());
cout<<perc.size()-1<<endl;
for(int i=0;i<perc.size();i++)cout<<perc[i]<<" ";
}