Pagini recente » Cod sursa (job #2659045) | Cod sursa (job #683527) | Cod sursa (job #852800) | Cod sursa (job #1005838) | Cod sursa (job #1002012)
#include <cstdio>
#include <list>
#include <vector>
#include <bitset>
#include <cstdlib>
using namespace std;
const int NMAX = 100003;
list <int> G[NMAX];
vector <int> S, R;
bitset <NMAX> viz;
int N;
inline bool is_connected () {
int cnode, s = 0;
list <int> :: iterator i;
S.push_back (1);
viz[1] = 1;
while (!S.empty ()) {
cnode = S.back ();
S.pop_back ();
++s;
for (i = G[cnode].begin (); i != G[cnode].end (); ++i)
if (!viz[*i])
viz[*i] = 1,
S.push_back (*i);
}
if (s != N)
return 0;
return 1;
}
inline void delete_edge (const int &node, const int &_node) {
for (list <int> :: iterator i = G[_node].begin (); i != G[_node].end (); ++i)
if (*i == node) {
G[_node].erase (i);
return;
}
}
inline void euler (int node) {
int w;
while (!G[node].empty ()) {
w = G[node].front ();
S.push_back (w);
delete_edge (node, w);
w = node;
node = G[w].front ();
G[w].pop_front ();
}
S.pop_back ();
}
inline void DFS () {
int cnode;
S.push_back (1);
while (!S.empty ()) {
cnode = S.back ();
euler (cnode);
R.push_back (S.back ());
}
}
int main () {
freopen ("ciclueuler.in", "r", stdin);
freopen ("ciclueuler.out", "w", stdout);
int M, i, a, b;
scanf ("%d%d", &N, &M);
for (i = 1; i <= M; ++i)
scanf ("%d%d", &a, &b),
G[a].push_back (b),
G[b].push_back (a);
for (i = 1; i <= N; ++i)
if (G[i].size () & 1)
printf ("-1"),
exit (EXIT_SUCCESS);
if (!is_connected ())
printf ("-1"),
exit (EXIT_SUCCESS);
DFS ();
for (i = 0; i < R.size () - 1; ++i)
printf ("%d ", R[i]);
}