Pagini recente » Cod sursa (job #2757490) | Cod sursa (job #3220291) | Cod sursa (job #1026194) | Cod sursa (job #904817) | Cod sursa (job #544222)
Cod sursa(job #544222)
#include<stdio.h>
#define N 100005
struct Nod {
int x;
Nod *next;
};
int n, m;
int list[N];
int gr[N];
int viz[N];
Nod* a[N];
void insert(Nod *&p, int q) {
Nod* t = new Nod();
t -> x = q;
t -> next = p;
p = t;
}
void find_tour(int s) {
for(Nod *it = a[s]; it; it = it -> next)
if (it -> x != -1) {
int n = it -> x;
for(Nod* it2 = a[it -> x]; it2 != 0; it2 = it2 -> next)
if (it2 -> x == s) {it2 -> x = -1; break;}
it -> x = -1;
find_tour(n);
}
list[++list[0]] = s;
}
int df(int s) {
viz[s] = 1;
for(Nod *it = a[s]; it; it = it -> next)
if (!viz[it->x])
df(it->x);
}
int este_conex() {
df(1);
for(int i = 1; i <= n; i++)
if (viz[i] == 0) return 0;
return 1;
}
int grad_par() {
for(int i = 1; i <= n; i++)
if (gr[i] % 2 != 0) return 0;
return 1;
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1; i <= m; i++) {
int u,v;
scanf("%d %d",&u,&v);
gr[u]++;
gr[v]++;
insert(a[u], v);
insert(a[v], u);
}
if (este_conex() && grad_par()) {
find_tour(1);
for(int i = 1; i < list[0]; i++)
printf("%d ",list[i]);
printf("\n");
}
else
printf("-1\n");
return 0;
}