Pagini recente » Cod sursa (job #2421170) | Cod sursa (job #2232520) | Monitorul de evaluare | Cod sursa (job #3171658) | Cod sursa (job #2417408)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 500000;
struct Edge {
int u, v;
int other(int x) {
return u ^ v ^ x;
}
}e[MAXM + 5];
vector<int>G[MAXN + 5];
int gr[MAXN + 5];
bool viz[MAXM + 5];
int stk[MAXM + 5], top;
void euler(int node) {
while (gr[node]) {
stk[++top] = node;
while (viz[G[node].back()] == 1)
G[node].pop_back();
viz[G[node].back()] = 1;
gr[node]--;
node = e[G[node].back()].other(node);
gr[node]--;
}
}
int main() {
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
e[i] = {u, v};
gr[u]++;
gr[v]++;
G[u].push_back(i);
G[v].push_back(i);
}
for (int i = 1; i <= n; ++i)
if (gr[i] % 2) {
printf("-1\n");
return 0;
}
euler(1);
printf("1 ");
while (1) {
euler(stk[top]);
if (top == 1)
break;
printf("%d ", stk[top]);
top--;
}
return 0;
}