Matita

1

applicando l’algoritmo “tour euleriano” questo problema totalizza 40/100. E’ l’algoritmo sbagliato oppure è sbagliata la mia soluzione? ho provato e riprovato più volte ma molti dei casi test risultano con “Arco inesistente” dove sbaglio? 

2

Non riesco proprio a capire dove sbaglio, eppure l’algoritmo dovrebbe essere quello (viene anche suggerito dalle assunzioni), è possibile che nelle soluzioni del correttore manchino cammini possibili? 

#include<cstdio>

#include<cstdlib>

#include<stack>

#include<list>

using namespace std;

int n,m,a,b;

int temp,temp1;

list<int>lista[200001];

stack<int>pila;

int grado[200001];

int fine;

int risultato[2000000];


void controlla(int att){


 <b>if</b>(grado[att]==0){                                                
                    fine++; 
                    risultato[fine]=att; 
                    <b>if</b>(!pila.empty()){
                    <b>int</b> prossimo=pila.top();
                    pila.pop();
                    controlla(prossimo);
                    }
                    <b>return</b>;
                     }
 <b>else</b>{
                           <b>for</b>(list&lt;<b>int</b>&gt;::iterator i=lista[att].begin();i==lista[att].begin();i=i){
                           lista[*i].remove(att);
                           lista[att].remove(*i);
                           grado[att]--;
                           grado[*i]--;                               
                           pila.push(att);
                           controlla(*i);
                           }  
                           }                   
 
 
 }



int main(){

FILE *in,*out;

in=fopen(“input.txt”,“r”);

fscanf(in,"%d %d %d %d",&n,&m,&a,&b);

for(int i=1;i<=m;i++){

fscanf(in,"%d %d",&temp,&temp1);

lista[temp].push_back(temp1);

lista[temp1].push_back(temp);

grado[temp]++;

grado[temp1]++;

}

fclose(in);

//fine input

pila.push(a);

controlla(a);

//fine controllo;

out=fopen(“output.txt”,“w”);

for(int i=m+1;i>1;i–)

fprintf(out,"%d %d\n",risultato[i],risultato[i-1]);

fclose(out);

//fine output


return 0;

}

P.s non badate tanto alla riga 

for(list<int>::iterator i=lista[att].begin();i==lista[att].begin();i=i){

non riuscivo proprio ad estrarre il primo elemento da una lista perciò ho fatto quella cosa bruttissima :P 

3

Non riesco a capire qual’è lo scopo del tuo algoritmo xD
Comunque non c’è bisogno di scomodare le list, bastano i vector!
E un’altra cosa: non è necessaria la pila, in quanto “esiste” già la ricorsiva che crea di suo uno stack!