Cod sursa(job #1098278)

Utilizator StexanIarca Stefan Stexan Data 4 februarie 2014 18:13:15
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#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;
}