Pagini recente » Istoria paginii runda/moisil2016-1112 | Cod sursa (job #3288724) | Cod sursa (job #2185348) | Cod sursa (job #3001457) | Cod sursa (job #2232271)
#include <stdio.h>
#define NMAX 100000
#define MMAX 500000
static struct edge {
int node;
int prev, next;
int compl;
} edges[2*MMAX+1];
static int adj[NMAX+1], sol[MMAX+1], nsol;
static int deg[NMAX+1];
static inline void ciclueuler(int v)
{
int compl, node;
while (adj[v] != 0) {
compl = edges[adj[v]].compl;
node = edges[adj[v]].node;
adj[v] = edges[adj[v]].next;
edges[adj[v]].prev = 0;
if (adj[node] == compl) {
adj[node] = edges[adj[node]].next;
edges[adj[node]].prev = 0;
} else {
edges[edges[compl].prev].next = edges[compl].next;
edges[edges[compl].next].prev = edges[compl].prev;
}
ciclueuler(node);
}
sol[nsol++] = v;
}
int main()
{
int n, m, u, v, i;
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &u, &v);
edges[2*i].node = v;
edges[2*i].next = adj[u];
edges[2*i].prev = 0;
edges[2*i].compl = 2*i+1;
edges[adj[u]].prev = 2*i;
adj[u] = 2*i;
deg[u]++;
if (u != v) {
deg[v]++;
edges[2*i+1].node = u;
edges[2*i+1].next = adj[v];
edges[2*i+1].prev = 0;
edges[2*i+1].compl = 2*i;
edges[adj[v]].prev = 2*i+1;
adj[v] = 2*i+1;
}
}
for (v = 1; v <= n; v++) {
if (deg[v] % 2) {
puts("-1");
return 0;
}
}
ciclueuler(1);
for (i = 0; i < nsol - 1; i++) {
printf("%d ", sol[i]);
}
return 0;
}