Pagini recente » Cod sursa (job #1467360) | Cod sursa (job #1995444) | Cod sursa (job #1278644) | Cod sursa (job #1683202) | Cod sursa (job #1098278)
#include <fstream>
#include <list>
#include <stack>
#include <vector>
using namespace std;
#define NMAX 100010
stack<int> S;
list<int> L[NMAX];
vector<int> Solutie;
int N,M,UsedNodes;;
bool Used[NMAX];
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
void UsualDFS(int Node){
Used[Node] = true;
UsedNodes++;
for (list<int>::iterator it = L[Node].begin(); it != L[Node].end() ; it++) {
if(!Used[*it]){
UsualDFS(*it);
}
}
}
void Delete(int Node, int Vecin){
L[Node].pop_front();
for (list<int>::iterator it = L[Vecin].begin(); it != L[Vecin].end() ; it++) {
if (*it == Node) {
L[Vecin].erase(it);
return;
}
}
}
void DFS(int Node){
while (!L[Node].empty()) {
int Vecin = L[Node].front();
S.push(Node);
Delete(Node,Vecin);
Node = Vecin;
}
}
void Read(){
f>>N>>M; int x,y;
for (int i = 1; i <= M; i++) {
f>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
}
void Solve(){
int Node = 1;
do{
DFS(Node);
Node = S.top(); S.pop();
Solutie.push_back(Node);
}while (!S.empty());
}
bool Check(){
UsualDFS(1);
for (int i = 1; i <= N; i++) {
if (Used[i] == 0) {
return false;
}
}
for (int i = 1; i <= N; i++) {
if (L[i].size()%2) {
return false;
}
}
return true;
}
void Write(){
for (vector<int>::iterator it = Solutie.begin(); it != Solutie.end(); it++) {
g<<*it<<" ";
}
}
int main()
{
Read();
if (!Check()) {
g<<-1<<"\n";
}else{
Solve();
Write();
}
return 0;
}