Pagini recente » infoarena - comunitate informatica, concursuri de programare | infoarena 2 | Cod sursa (job #1281818) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #1133005)
/*
* File: main.cpp
* Author: guest-xR8Lu6
*
* Created on 3. maaliskuuta 2014, 10:44
*/
#include <iostream>
#include <vector>
#include <map>
#include <cassert>
#include <fstream>
#define cin input
#define cout output
using namespace std;
ifstream input ("ciclueuler.in");
ofstream output("ciclueuler.out");
struct Node
{
map<int, int> paths;
};
vector<Node> nodes;
int nodeCount, edgeCount;
vector<int> route;
void go(int i)
{
while(nodes[i].paths.size() > 0)
{
map<int, int>::iterator it = nodes[i].paths.begin();
int j = it->first;
it->second--;
if(it->second == 0)
{
nodes[i].paths.erase(j);
}
if(i != j)
{
nodes[j].paths[i]--;
if(nodes[j].paths[i] == 0)
nodes[j].paths.erase(i);
}
go(j);
}
route.push_back(i);
}
int main()
{
cin >> nodeCount >> edgeCount;
nodes.resize(nodeCount);
for(int i = 0; i < edgeCount; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
nodes[a].paths[b]++;
if(a != b) nodes[b].paths[a]++;
}
for(int i = 0; i < nodeCount; i++)
{
int total = 0;
for(map<int, int>::iterator it = nodes[i].paths.begin(); it != nodes[i].paths.end(); it++)
{
if(it->first == i)
total += it->second;
total += it->second;
}
if(total % 2 != 0)
{
cout << "-1" << endl;
return 0;
}
}
go(0);
for(int i = 0; i < route.size() - 1; i++)
{
cout << (i ? " " : "") << route[i] + 1;
}
cout << endl;
return 0;
}