Pagini recente » Cod sursa (job #111405) | Cod sursa (job #170110) | Cod sursa (job #2922588) | Cod sursa (job #203118) | Cod sursa (job #575165)
Cod sursa(job #575165)
#include <fstream>
#include <vector>
#define mp make_pair
using namespace std;
ifstream in ("ciclueuler.in");
ofstream out ("ciclueuler.out");
const int N = 100010;
vector <int> v, rez;
vector <pair <int, int> > L[N];
int n, gr[N];
bool used[5 * N];
void read() {
int m, x, y;
in >> n >> m;
for (int i = 1; i <= m; ++ i) {
in >> x >> y;
L[x].push_back(mp(y,i));
L[y].push_back(mp(x,i));
}
}
bool verif() {
for (int i = 1; i <= n; ++ i)
if (L[i].size() % 2 == 1)
return false;
return true;
}
void ciclu_euler() {
int nc;
bool ok;
v.push_back(1);
while (! v.empty()) {
ok = false;
nc = *(-- v.end());
for (vector <pair <int, int> > :: iterator it = L[nc].begin(); it != L[nc].end(); ++ it)
if (! used[it -> second]) {
used[it -> second] = 1;
v.push_back(it -> first);
ok = true;
break;
}
if (ok == false) {
rez.push_back(nc);
v.pop_back();
}
}
}
void afis() {
vector <int> :: iterator it = rez.end();
-- it;
for (it = it; it != rez.begin(); -- it)
out << *it << ' ';
}
int main() {
read();
if (! verif()) {
out << "-1\n";
return 0;
}
ciclu_euler();
afis();
return 0;
}