Pagini recente » Cod sursa (job #631049) | Cod sursa (job #340542) | Cod sursa (job #919678) | Cod sursa (job #1230660) | Cod sursa (job #1414648)
#include <fstream>
#include <list>
#define NMAX 100005
#define MMAX 500005
using namespace std;
struct edge {
int a, b;
bool vis;
edge (int _a = 0, int _b = 0, bool _vis = false): a(_a), b(_b), vis(_vis) {}
inline int other (int node) {
return a + b - node;
}
} edges[MMAX];
list <int> graph[NMAX];
list <int> sol;
list <int> :: iterator before;
inline void expand (int node) {
int new_node;
while (!graph[node].empty())
if (edges[graph[node].front()].vis)
graph[node].pop_front();
else {
new_node = edges[graph[node].front()].other(node);
edges[graph[node].front()].vis = true;
graph[node].pop_front();
node = new_node;
sol.insert(before, node);
}
}
inline void euler () {
sol.push_back(1);
for (list <int> :: iterator it = sol.begin(); it != sol.end(); it++) {
before = (++ it); it--;
expand(*it);
}
}
int main()
{
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int n = 0, m = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].a >> edges[i].b;
graph[edges[i].a].push_back(i);
graph[edges[i].b].push_back(i);
}
euler();
if (sol.size() != m + 1)
cout << "-1\n";
else {
list <int> :: iterator it = sol.begin();
it ++;
cout << *it;
for (it++; it != sol.end(); it++)
cout << ' ' << *it;
cout << '\n';
}
cin.close();
cout.close();
return 0;
}