Pagini recente » Cod sursa (job #886925) | Cod sursa (job #727318) | Cod sursa (job #93887) | Cod sursa (job #2904181) | Cod sursa (job #2049445)
#include <fstream>
#include <vector>
#define file "ciclueuler"
#define N 100003
using namespace std;
ifstream fin(file".in");
ofstream fout(file".out");
struct nod{
int info;
nod *urm;
}*p[N],*u[N];
int n,m,x,y;
int gr[N];
bool Ciclu()
{
for(int i=1; i<=n; ++i)
if(gr[i] == 0 || gr[i]%2 != 0) return 0;
return 1;
}
int sol[5*N],nsol;
inline void elim(const int &nod,const int &x)
{
bool gasit = false;
for(::nod *c = p[nod]; !gasit && c != NULL; c = c->urm)
if(c->info == x)
{
gasit = true;
c->info = -1;
}
}
inline void Euler(int nod)
{
::nod *c = p[nod];
for(; c != NULL; c = c->urm)
{
if(c->info == -1) continue;
int nodurm = c->info;
elim(c->info,nod);
c->info = -1;
Euler(nodurm);
sol[++nsol] = nod;
}
}
inline void add_nod(const int &x,const int &y)
{
nod *c = new nod;
c->urm = NULL;
c->info = y;
if(p[x] == NULL)
p[x] = u[x] = c;
else
{
u[x]->urm = c;
u[x] = c;
}
}
void afisare()
{
for(int i=1; i<=n; ++i)
{
fout<<i<<" : ";
for(::nod *c = p[i]; c != NULL; c = c->urm)
fout<<c->info<<" ";
fout<<"\n";
}
}
int main()
{
fin>>n>>m;
while(m--)
{
fin>>x>>y;
add_nod(x,y);
if(x != y)
add_nod(y,x);
++gr[x];
++gr[y];
}
//afisare();
if(Ciclu())
{
Euler(1);
for(int i=1; i<=nsol; ++i)
fout<<sol[i]<<" ";
}
else fout<<"-1\n";
fin.close(); fout.close();
return 0;
}