Pagini recente » Cod sursa (job #2466315) | Cod sursa (job #1931393) | Cod sursa (job #1751561) | Cod sursa (job #1976439) | Cod sursa (job #2427995)
#include <stack>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
struct muchie {
int nrMuchie, nod;
};
vector<int>ciclu;
const int dim = 100001;
int grade[dim];
int noduri, muchii;
vector<muchie>G[dim];
stack<int>s;
int sters[500001];
void input() {
int c = 0;
in >> noduri >> muchii;
for (int p = 0; p < muchii; p++) {
int i, j;
in >> i >> j;
++c;
grade[i]++, grade[j]++;
muchie x;
x.nod = j;
x.nrMuchie = c;
G[i].push_back(x);
x.nod = i;
G[j].push_back(x);
}
return;
}
void euler() {
s.push(1);
while (s.empty() == false) {
int nod = s.top();
if (G[nod].size()) {
int nrM = G[nod].back().nrMuchie;
int node = G[nod].back().nod;
G[nod].pop_back();
if (!sters[nrM]) {
sters[nrM] = true;
s.push(node);
}
}
else {
ciclu.push_back(nod);
s.pop();
}
}
return;
}
int main() {
input();
for (int i = 1; i <= noduri; i++) {
if (grade[i] & 1) {
out << "-1";
return 0;
}
}
euler();
int x = ciclu.size();
for (int i = 0; i < x - 1; i++) {
out << ciclu[i] << " ";
}
return 0;
}