Pagini recente » Cod sursa (job #1582323) | Cod sursa (job #2541160) | Cod sursa (job #1420400) | Cod sursa (job #2549492) | Cod sursa (job #1361095)
// ciclueuler
#include <iostream>
#include <fstream>
#include <vector>
#define pb push_back
#define NMax 100005
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n, m;
vector<int> V[NMax];
vector<int> sol;
int node;
int vecin;
vector<int> old;
unsigned i;
void read() {
f>>n>>m;
for (int i=1;i<=m;i++) {
int a, b;
f>>a>>b;
V[a].pb(b);
V[b].pb(a);
}
}
void go() {
old.push_back(node);
while (!V[node].empty()) {
vecin = V[node][V[node].size()-1];
V[node].pop_back();
for (i=0;i<V[vecin].size();i++)
if (V[vecin][i] == node) {
V[vecin].erase(V[vecin].begin() + i);
break;
}
node = vecin;
go();
node = old[old.size()-1];
}
old.pop_back();
sol.pb(node);
}
bool viz[NMax];
void dfs(int node) {
viz[node] = true;
for (int i=0;i<V[node].size();i++)
if (!viz[V[node][i]])
dfs(V[node][i]);
}
bool isEuler() {
bool ok1 = true;
for (int i=1;i<=n;i++)
if (V[i].size()%2 != 0)
ok1 = false;
if (!ok1) return false;
dfs(1);
for (int i=1;i<=n;i++)
if (!viz[i]) {
return false;}
return true;
}
int main() {
read();
if (isEuler()) {
node=1;go();
sol.pop_back();
for (auto i=sol.begin();i!=sol.end();i++)
g<<(*i)<<' ';
}else {
g<<-1<<'\n';
}
f.close(); g.close();
return 0;
}