Pagini recente » Cod sursa (job #2203922) | Cod sursa (job #3254398) | Borderou de evaluare (job #169905) | Cod sursa (job #2618904) | Cod sursa (job #815492)
Cod sursa(job #815492)
#include <cstdio>
#include <cstring>
#include <list>
#include <stack>
#include <vector>
using namespace std;
inline int next_int() {
int n = 0;
char c = getchar_unlocked();
while (!('0' <= c && c <= '9')) {
c = getchar_unlocked();
}
while ('0' <= c && c <= '9') {
n = n * 10 + c - '0';
c = getchar_unlocked();
}
return n;
}
const int V = 100000 + 1;
const int E = 500000 + 500000;
int deg[V], root[V], seen[E];
list<int> G[V];
vector<int> tour;
stack<int> stk;
int find(int u) {
return (root[u] == u) ? (u) : (root[u] = find(root[u]));
}
inline void merge(int u, int v) {
root[find(u)] = find(v);
}
inline void cycle(int u) {
while (!G[u].empty()) {
stk.push(u);
int v = G[u].front(); G[u].pop_front();
for (list<int>::iterator it = G[v].begin(); it != G[v].end(); it++) {
if (*it == u) {
G[v].erase(it);
break;
}
}
u = v;
}
}
inline void find_euler_tour(int u) {
stk.push(u);
while (!stk.empty()) {
u = stk.top(); stk.pop();
cycle(u);
tour.push_back(u);
}
}
int main() {
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
const int n = next_int();
const int m = next_int();
for (int i = 1; i <= n; i++) {
root[i] = i;
}
for (int i = 0; i < m; i++) {
int u = next_int(), v = next_int();
deg[u]++, deg[v]++;
G[u].push_back(v), G[v].push_back(u);
merge(u, v);
}
int eulerian = true;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) || find(i) != find(1)) {
eulerian = false;
}
}
if (eulerian) {
find_euler_tour(1);
for (int i = tour.size() - 1; i >= 0; i--) {
printf("%d ", tour[i]);
}
} else {
printf("-1");
}
return 0;
}