Ciao a tutti,
è da un po di tempo che provo a risolvere senza successo questo problema. A quanto ho capito si tratta di un eulerian path, ma nonostante questo ottengo vari errori come “output malformato”(nel primo testacse),“arco inesistente”,“arco doppio”,“killed with signal 11” e TLE negli ultimi due testcase. Ho provato molti input localmente ma non riesco a capire dove sia l’errore dato che risponde sempre giustamente. La mia idea era di provare ogni percorso visitando il grafo e fermandomi se mi ritrovo in un vicolo cieco oppure se uso tutti gli archi che partono dal nodo di arrivo e ne avanzano ancora alcuni.
Ecco il codice:
#include<iostream>
#include<vector>
#include<deque>
#include<list>
using namespace std;
bool fine=false;
list<int> grafo[100001];
vector<int> sol(0);
int num,archi,b,e,ora=0,grado=0;
void visita(int k){
if(grado==0&&ora!=archi)
return;
//cout<<k<<endl;
if(fine==false){
if(ora==archi&&k==e){
fine=true;
printf("%d ",b);
for(int i=1;i<sol.size();i++)
printf("%d\n%d ",sol[i],sol[i]);
printf("%d",e);
}
else{
int h;
//cout<<"Sono al nodo "<<k<<endl;
list<int>::iterator z;
if(grafo[k].size()!=0)
z=grafo[k].end();
if(grafo[k].size()!=0)
z--;
sol.push_back(k);
ora++;
for(int i=grafo[k].size()-1;i>=0&&fine==false;i--,z--){
grafo[k].remove(*z);
grafo[*z].remove(k);
if(*z==e)
grado--;
//cout<<"vado al nodo "<<h<<endl;
visita(*z);
if(fine==true)
return;
//cout<<"Sono di nuovo al nodo "<<k<<endl;
if(*z==e)
grado++;
grafo[k].push_back(*z);
grafo[*z].push_back(k);
}
ora--;
if(sol.size()!=0)
sol.erase(sol.begin()+sol.size()-1);
}
}
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&num);
scanf("%d",&archi);
scanf("%d",&b);
scanf("%d",&e);
int a,l;
for(int i=0;i<archi;i++){
scanf("%d",&a);
scanf("%d",&l);
grafo[a].push_back(l);
grafo[l].push_back(a);
if(a==e||l==e)
grado++;
}
visita(b);
return 0;
}
Credo che mi basti anche un esempio di input, in modo da poter vedere dove si trova l’errore
