Pagini recente » Cod sursa (job #192096) | Cod sursa (job #1958115) | Cod sursa (job #2135443) | Cod sursa (job #979162) | Cod sursa (job #1098248)
//
// main.cpp
// Ciclu Eulerian
//
// Created by Stefan Iarca on 2/4/14.
// Copyright (c) 2014 Stefan Iarca. All rights reserved.
//
/*
Algoritmul utilizeaza o stiva unde se pun noduri
Acestea se scot din stiva si se pun in solutie
*/
#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;
bool Used[NMAX];
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
void UsualDFS(int Node){
Used[Node] = true;
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);
break;
}
}
}
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(){
DFS(1);
for (int i = 1; i <= N; i++) {
if (!Used[i]) {
return false;
}
}
for (int i = 1; i <= N; i++) {
if (L[i].size()%2 == 1) {
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;
return 0;
}
Solve();
Write();
return 0;
}