Pagini recente » Cod sursa (job #2748086) | Cod sursa (job #1635311) | Cod sursa (job #2739009) | Cod sursa (job #3293859) | Cod sursa (job #498873)
Cod sursa(job #498873)
#include <cstdio>
#include <list>
#include <stack>
#include <queue>
using namespace std;
#define NMAX 100050
int grad[NMAX], viz[NMAX], n, m, i, x, y, nod;
list <int> G[NMAX], E;
queue <int> Q;
stack <int> S;
int eulerian (); void ciclu (int);
int main () {
freopen ("ciclueuler.in", "r", stdin);
freopen ("ciclueuler.out", "w", stdout);
scanf ("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
grad[x]++, grad[y]++;
G[x].push_back (y), G[y].push_back (x);
}
if (eulerian ()) {
nod = 1;
do {
ciclu (nod);
nod = S.top (), S.pop ();
E.push_back (nod);
} while (!S.empty ());
for (list <int>::iterator it = E.begin (); it != E.end (); it++)
printf ("%d ", *it);
}
else
printf ("-1");
return 0;
}
int eulerian () {
int nod;
list <int>::iterator it;
Q.push (1), viz[1] = 1;
while (!Q.empty ()) {
nod = Q.front (), Q.pop ();
for (it = G[nod].begin (); it != G[nod].end (); it++)
if (!viz[*it])
Q.push (*it), viz[*it] = 1;
}
for (i = 1; i <= n; i++)
if (!viz[i] || grad[i] % 2) return 0;
return 1;
}
void sterge (int x, int y) {
list <int>::iterator it;
grad[x]--, grad[y]--;
G[x].pop_front ();
for (it = G[y].begin (); it != G[y].end (); it++)
if (*it == x) {
G[y].erase (it);
return;
}
}
void ciclu (int nod) {
int fiu;
while (!G[nod].empty ()) {
fiu = G[nod].front ();
S.push (nod);
sterge (nod, fiu);
nod = fiu;
}
}