Cod sursa(job #881928)
#include <fstream>
#include <vector>
#define DMAX 10010
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m, 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 grade_pare();
void determina_eulerian();
void afisare_ciclu();
int ciclu(int x, lista& c, lista& sfc);
int main()
{
citire();
if(conex() && grade_pare())
{
determina_eulerian();
afisare_ciclu();
}
else fout<<"-1"<<'\n';
fout.close();
return 0;
}
void citire()
{
int i,x,y;
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);
}
}
bool conex()
{
int i, x;
for(x=1; x<=n && !d[x]; x++);
if(x>n) return 1;
//x e varf neizolat
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 grade_pare()
{
int i;
for(i=1; i<=n; i++)
if(d[i]%2) return 0;
return 1;
}
void determina_eulerian()
{
//caut un vf cu gradul nenul
int x, total, nr2;
lista p, q;
for(x=1; x<=n && !d[x]; x++);
//x are grad nenul
total=ciclu(x, c1, sfc1);
while(total<m)
{
//caut pe c1 un varf cu grad nenul
for(p=c1; !d[p->vf]; p=p->urm);
//acum p indica un varf cu grad nenul
nr2=ciclu(p->vf, c2, sfc2);
//reunesc cele doua cicluri
q=p->urm; p->urm=c2->urm; sfc2->urm=q;
total+=nr2;
}
}
int ciclu(int x, lista& c, lista& sfc)
{
//incepem ciclul cu varful x
lista p;
int y, uvf, lg=0, i, j;
//aloc memorie pt un nod
p=new nod;
p->vf=x; p->urm=NULL;
c=sfc=p;//el este singurul, primul, ultimul nod din lista
do
{
//caut y un varf adiacent cu ultimul varf din lista
uvf=sfc->vf;
//parcurg linia uvf pana gasesc un y adiacent cu uvf
for(i=0; i<G[uvf].size(); i++)
if(G[uvf][i]!=0) break;
y=G[uvf][i];
//adaug muchia (uvf,y) in ciclul eulerian
//aloc memorie pt un nou vf
p=new nod;
p->vf=y; p->urm=NULL;
//il adaug la sfarsitul ciclului
sfc->urm=p; sfc=p;
lg++;
//am folosit o muchie si o elimin din graf
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';
}