Pagini recente » Cod sursa (job #2564443) | Cod sursa (job #2934251) | Cod sursa (job #2902610) | Cod sursa (job #2925419) | Cod sursa (job #969027)
Cod sursa(job #969027)
#include <list>
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector <bool> viz;
vector <int> G, sol;
vector <list <int> > g;
int n, m;
bool res = 1;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
void dfs(int x) {
viz[x] = 1;
for (list <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
if (!viz[*it])
dfs (*it);
}
bool grad() {
for (int i = 1; i <= n; ++i)
if (G[i] % 2 || (!viz[i] && G[i]))
return 0;
return 1;
}
void euler(int x) {
while (g[x].size()) {
int y = *g[x].begin();
g[x].erase(g[x].begin());
list <int> :: iterator it = g[y].begin();
while (*it != x)
++it;
g[y].erase (it);
euler(y);
sol.push_back (x);
}
}
int main() {
fin >> n >> m;
viz.resize(n+1);
G.resize(n+1);
g.resize(n+1);
sol.reserve(m);
while (m--) {
int x, y;
fin >> x >> y;
if (x != y)
G[x]++, G[y]++;
g[x].push_back (y);
g[y].push_back (x);
}
fin.close();
int x = 1;
while (!g[x].size() && x <= n)
++x;
dfs(x);
res = grad();
if (res) {
euler(x);
for (int i = 1; i <= n; ++i)
if (g[i].size())
res = 0;
}
if (res)
for (vector <int> :: reverse_iterator it = sol.rbegin(); it != sol.rend(); ++it)
fout << *it << " ";
else
fout << -1;
fout.close();
}