Pagini recente » Borderou de evaluare (job #1180752) | Borderou de evaluare (job #2360129) | Borderou de evaluare (job #916537) | Borderou de evaluare (job #1239087) | Cod sursa (job #1414655)
#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 int 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);
}
return node;
}
inline bool euler () {
sol.push_back(1);
for (list <int> :: iterator it = sol.begin(); it != sol.end(); it++) {
before = (++ it); it--;
if (expand(*it) != *it)
return false;
}
return true;
}
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);
}
if (!euler())
cout << "-1\n";
else 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;
}