Pagini recente » Cod sursa (job #2138213) | Cod sursa (job #2377677) | Cod sursa (job #2327325) | Cod sursa (job #2698671) | Cod sursa (job #575176)
Cod sursa(job #575176)
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;
ifstream in ("ciclueuler.in");
ofstream out ("ciclueuler.out");
const int N = 100010;
vector <int> rez;
list <int> L[N];
stack <int> s;
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(y);
L[y].push_back(x);
}
}
bool verif() {
for (int i = 1; i <= n; ++ i)
if (L[i].size() & 1)
return false;
return true;
}
void sterge(int a, int b) {
L[a].pop_back();
for (list <int> :: iterator it = L[b].begin() ; it != L[b].end(); ++ it)
if(*it == a) {
L[b].erase(it);
break;
}
}
void euler(int nc) {
int newn;
while (1) {
if (L[nc].empty())
break;
newn = L[nc].back();
s.push(nc);
sterge(nc, newn);
nc = newn;
}
}
void ciclu_euler() {
int v = 1;
do {
rez.push_back(v);
euler(v);
v = s.top();
s.pop();
}
while (!s.empty());
}
void afis() {
for (vector <int> :: iterator it = rez.begin(); it != rez.end(); ++ it)
out << *it << ' ';
}
int main() {
read();
if (! verif()) {
out << "-1\n";
return 0;
}
ciclu_euler();
afis();
return 0;
}