Pagini recente » Cod sursa (job #2152298) | Cod sursa (job #176296) | Cod sursa (job #1634467) | Cod sursa (job #2044685) | Cod sursa (job #369175)
Cod sursa(job #369175)
#include <stdio.h>
using namespace std;
#define nmax 100001
struct graf
{
int x;
graf *urm;
};
graf *G[nmax],*s;
int n,m,gr[nmax],nc;
bool viz[nmax];
void add(graf *&nod,int nr)
{
graf *p=new graf;
p->x=nr;
p->urm=nod;
nod=p;
}
int pop(graf *&g)
{
int x;
graf *p=g;
x=p->x;
g=g->urm;
delete p;
return x;
}
void del(graf *&g,int x)
{
graf *p=g,*pre=NULL;
while(p)
{
if(p->x==x)
{
if(pre)
pre->urm=p->urm;
else
g=g->urm;
delete p;
return;
}
pre=p;
p=p->urm;
}
}
void read()
{
FILE *f=fopen("ciclueuler.in","r");
fscanf(f,"%d %d",&n,&m);
int x,y;
for(int i=0;i<m;i++)
{
fscanf(f,"%d %d",&x ,&y);
add(G[x],y);
++gr[x];
add(G[y],x);
++gr[y];
}
}
void dfs(int nod)
{
++nc;
viz[nod]=true;
graf *p=G[nod];
for(;p!=NULL;p=p->urm)
if(!viz[p->x])
dfs(p->x);
}
bool conex()
{
dfs(1);
if(nc==n)
return true;
return false;
}
void euler()
{
int nod=1,y;
while(G[nod])
{
y=pop(G[nod]);
del(G[y],nod);
add(s,y);
nod=y;
}
}
bool eulerian()
{
int i;
if(conex())
for(i=1;i<=n;i++)
{
if(gr[i]%2)
return false;
}
else
return false;
return true;
}
void solve()
{
FILE *g=fopen("ciclueuler.out","w");
if(!eulerian())
fprintf(g,"-1");
else
{
euler();
for(graf *p=s;p!=NULL;p=p->urm)
fprintf(g,"%d ",p->x);
}
}
int main()
{
read();
solve();
}