Pagini recente » Cod sursa (job #453371) | Cod sursa (job #3154471) | Cod sursa (job #2476688) | Cod sursa (job #2454941) | Cod sursa (job #1342595)
// ciclueuler
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#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];
bool viz[NMax];
stack<int> S;
vector<int> sol;
void dlt(int x, int y) {
V[x].pop_back();
for (unsigned i=0;i<V[y].size();i++)
if (V[y][i] == x) {
V[y].erase(V[y].begin()+i);
return;
}
}
void read() {
f>>n>>m;
for (int i=1;i<=m;i++) {
int x, y;
f>>x>>y;
V[x].pb(y);
V[y].pb(x);
}
}
void dfs(int node) {
viz[node] = true;
for (unsigned i=0;i<V[node].size();i++) {
int vecin = V[node][i];
if (!viz[vecin])
dfs(vecin);
}
}
bool conex() {
dfs(1);
for (int i=1;i<=n;i++)
if (!viz[i])
return false;
return true;
}
void goEuler(int node) {
while (true) {
if (V[node].empty())
break;
int v = V[node][V[node].size()-1];
S.push(node);
V[node].pop_back();
for (int i=0;i<V[v].size();i++)
if (V[v][i] == node) {
V[v].erase(V[v].begin()+i);
break;
}
node = v;
}
}
void solve() {
if (!conex()) {
g<<-1<<'\n';
return;
}
bool admite;
admite = true;
for (int i=1;i<=n && admite;i++)
if (V[i].size()%2 != 0)
admite = false;
if (!admite) {
g<<-1<<'\n';
return;
}
int v = 1;
do {
goEuler(v);
v = S.top(); S.pop();
sol.pb(v);
} while (!S.empty());
}
int main() {
read();
solve();
for (unsigned i=0;i<sol.size();i++)
g<<sol[i]<<' ';
f.close(); g.close();
return 0;
}