Cod sursa(job #882133)
#include <cstdio>
#include <vector>
#define DMAX 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m;
int d[DMAX];
bool viz[DMAX];
vector<int>G[DMAX];
struct nod { int vf; struct nod * urm;};
typedef struct nod * Lista;
Lista c1,c2,sfc1,sfc2;
void citire();
void dfs(int x);
bool conex();
int gradepare();
void determina_eulerian();
void afisare_ciclu();
int ciclu(int x,Lista& c,Lista& sfc);
int main()
{
citire();
if(conex() && gradepare())
{
determina_eulerian();
afisare_ciclu();
}
else
fout<<"-1\n";
fout.close();
return 0;
}
bool conex()
{
int i,x;
for(x=1;x<=n && !d[x];x++);
if(x>n) return 1;
dfs(x);
for(i=1;i<=n;i++)
if(!viz[i] && d[i]) return 0;
return 1;
}
void dfs(int x)
{
int i;
viz[x]=true;
for(i=0;i<G[x].size();i++)
if(viz[G[x][i]]==0)
dfs(G[x][i]);
}
int gradepare()
{
int i;
for(i=1;i<=n;i++)
if(d[i]%2) return 0;
return 1;
}
void citire()
{
int x, y, i;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
d[x]++; d[y]++;
G[x].push_back(y);
G[y].push_back(x);
}
}
void determina_eulerian()
{
int x,total,nr2;
Lista p,q;
for(x=1;x<=n && !d[x];x++);
total=ciclu(x,c1,sfc1);
while(total<m)
{
for(p=c1; !d[p->vf];p=p->urm);
nr2=ciclu(p->vf,c2,sfc2);
q=p->urm; p->urm=c2->urm; sfc2->urm=q;
total+=nr2;
}
}
int ciclu(int x, Lista& C, Lista& sfC)
{
Lista p;
int y, lg=0, i, j, uvf;
p=new nod;
p->vf=x; p->urm=NULL;
C=sfC=p;
do
{
uvf=sfC->vf;
for(i=0; i<G[uvf].size();i++)
if( G[uvf][i]!=0)
break;
y=G[uvf][i];
p=new nod;
p->vf=y; p->urm=NULL;
sfC->urm=p; sfC=p;
lg++;
G[uvf][i]=0;
for(j=0;j<G[y].size();j++)
if(G[y][j]==uvf)
{
G[y][j]=0; break;
}
d[uvf]--; d[y]--;
}
while(y!=x);
return lg;
}
void afisare_ciclu()
{
Lista p;
for(p=c1;p;p=p->urm)
fout<<p->vf<<' ';
fout<<'\n';
}