Pagini recente » Cod sursa (job #627102) | Cod sursa (job #1810961) | Cod sursa (job #3254685) | Cod sursa (job #1798287) | Cod sursa (job #1602127)
#include<cstdio>
using namespace std;
const int nMax = 100000, mMax = 500000;
int muchie[mMax * 2 + 1], nodV[mMax * 2 + 1], urm[mMax * 2 + 1], lst[nMax + 1], sol[mMax + 1];
bool viz[nMax], ut[mMax + 1], grad[nMax + 1];
int st[mMax + 1];
int nr = 0, nrS = 0, vf = 0;
FILE *in, *out;
inline void adauga(int i, int x, int y){
nodV[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
muchie[nr] = i;
}
void dfs(){
int nod, pos, vec, posp;
while(vf){
nod = st[vf - 1];
pos = lst[nod];
viz[nod] = true;
vec = 0;
if(lst[nod]){
while(pos && !vec){
if(!ut[muchie[pos]]){
ut[muchie[pos]] = true;
vec = nodV[pos];
}
//sterge
if(ut[muchie[pos]]){
if(pos == lst[nod]){
lst[nod] = urm[pos];
}else{
urm[posp] = urm[pos];
}
}
posp = pos;
pos = urm[pos];
}
if(vec) st[vf++] = vec;
}else{
sol[++nrS] = nod;
vf--;
}
}
}
int main (){
in = fopen("ciclueuler.in","r");
out = fopen("ciclueuler.out","w");
int n, m; fscanf(in,"%d%d", &n, &m);
for(int i = 1, x, y; i <= m ; ++i){
fscanf(in,"%d%d", &x, &y);
adauga(i, x, y);
adauga(i, y, x);
grad[x] = 1 - grad[x];
grad[y] = 1 - grad[y];
}
st[vf++] = 1;
dfs();
for(int i = 1 ; i <= n ; ++i){
if(!viz[i] || grad[i]){
fprintf(out,"-1\n");
return 0;
}
}
for(int i = nrS ; i > 1 ; --i)
fprintf(out,"%d ", sol[i]);
fprintf(out,"\n");
return 0;
}