Pagini recente » Cod sursa (job #2920088) | Cod sursa (job #292402) | Cod sursa (job #700774) | Cod sursa (job #2638325) | Cod sursa (job #2544622)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
int n, m, x, y, nr;
int from[500005], to[500005], ciclu[500005];
bool viz[100005];
vector <int> v[100005];
void dfs(int nod) {
viz[nod] = true;
int w;
for (auto it : v[nod]) {
if (nod == to[it])
w = from[it];
else
w = to[it];
if (!viz[w])
dfs(w);
}
}
bool conex() {
for (int i = 1; i <= n; ++i)
if (!viz[i])
return false;
return true;
}
bool grad_par() {
for (int i = 1; i <= n; ++i)
if (v[i].size() % 2 == 1)
return false;
return true;
}
void euler(int nod) {
int w;
for (auto it : v[nod]) {
if (to[it] == 0)
continue;
if (to[it] == nod)
w = from[it];
else
w = to[it];
to[it] = from[it] = 0;
euler(w);
}
ciclu[++nr] = nod;
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
v[x].push_back(i);
v[y].push_back(i);
from[i] = x;
to[i] = y;
}
dfs(1);
if (!conex() || !grad_par()) {
fout << -1;
return 0;
}
euler(1);
for (int i = 1; i < nr; ++i)
fout << ciclu[i] << ' ';
return 0;
}