#include <iostream>
using namespace std;
int lunghezza=0;
const int LungRiga=2;
int M;
int Ragnatela[100][LungRiga];
int percorso[10000];
bool trovato=false;
void VaiAvanti(int Nodo,int indice)
{
for (int i=0;i<M;i++)
{
for (int j=0;j<LungRiga;j++)
{
if (Ragnatela[i][j]==Nodo)//serve per controllare tutti i vari collegamenti che ogni nodo ha con gli altri nodi
{
if (trovato)
{
return;
}
if (j==0)
{
int NuovoNodo=Ragnatela[i][j+1];
if (NuovoNodo==percorso[indice-2]&&indice>1)
{
return;
}
percorso[indice]=NuovoNodo;
if(NuovoNodo==0&&indice%2!=0)
{
trovato=true;
lunghezza=indice;
return;
}
VaiAvanti(NuovoNodo,indice+1);
}
if (j==1)
{
int NuovoNodo=Ragnatela[i][j-1];
if (NuovoNodo==percorso[indice-2]&&indice>1)
{
return;
}
percorso[indice]=NuovoNodo;
if(NuovoNodo==0&&indice%2!=0)
{
trovato=true;
lunghezza=indice;
return;
}
VaiAvanti(NuovoNodo,indice+1);
}
}
}
}
return;
}
int main(int argc, char** argv) {
int N;
cin>>N>>M;
for (int i=0;i<M;i++)
{
for (int j=0;j<LungRiga;j++)
{
cin>>Ragnatela[i][j];
}
}
percorso[0]=0;
VaiAvanti(0,1);
cout<<lunghezza<<endl;
for (int i=0;i<=lunghezza;i++)
{
cout<<percorso[i]<<" ";
}
return 0;
}
l'algoritmo trova un percorso che esiste ed è anche lungo quanto quello dei test però non funziona perche esistono più percorsi della stessa lunghezza diversi ma giusti
[/quote]
[quote="ubaldo, post:1, topic:6637, full:true"]
#include <iostream>
using namespace std;
int lunghezza=0;
const int LungRiga=2;
int M;
int Ragnatela[100][LungRiga];
int percorso[10000];
bool trovato=false;
void VaiAvanti(int Nodo,int indice)
{
for (int i=0;i<M;i++)
{
for (int j=0;j<LungRiga;j++)
{
if (Ragnatela[i][j]==Nodo)//serve per controllare tutti i vari collegamenti che ogni nodo ha con gli altri nodi
{
if (trovato)
{
return;
}
if (j==0)
{
int NuovoNodo=Ragnatela[i][j+1];
if (NuovoNodo==percorso[indice-2]&&indice>1)
{
return;
}
percorso[indice]=NuovoNodo;
if(NuovoNodo==0&&indice%2!=0)
{
trovato=true;
lunghezza=indice;
return;
}
VaiAvanti(NuovoNodo,indice+1);
}
if (j==1)
{
int NuovoNodo=Ragnatela[i][j-1];
if (NuovoNodo==percorso[indice-2]&&indice>1)
{
return;
}
percorso[indice]=NuovoNodo;
if(NuovoNodo==0&&indice%2!=0)
{
trovato=true;
lunghezza=indice;
return;
}
VaiAvanti(NuovoNodo,indice+1);
}
}
}
}
return;
}
int main(int argc, char** argv) {
int N;
cin>>N>>M;
for (int i=0;i<M;i++)
{
for (int j=0;j<LungRiga;j++)
{
cin>>Ragnatela[i][j];
}
}
percorso[0]=0;
VaiAvanti(0,1);
cout<<lunghezza<<endl;
for (int i=0;i<=lunghezza;i++)
{
cout<<percorso[i]<<" ";
}
return 0;
}
l’algoritmo trova un percorso che esiste ed è anche lungo quanto quello dei test però non funziona perche esistono più percorsi della stessa lunghezza diversi ma giusti
