Cod sursa(job #913191)

Utilizator Theorytheo .c Theory Data 13 martie 2013 10:19:40
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<stack>
#include<list>

using namespace std;

const int Nmax = 100009;
const int Mmax = 500009;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int N; int M;

stack<int> S;

list<int> G[Nmax];

void Read(){

    fin >> N >> M;
    for(int i = 1; i <= M; ++i){
       int X; int Y;
       fin >> X >> Y;

       G[X].push_back(Y);
       G[Y].push_back(X);
    }
}

void Euler(int Nod){

    while(!G[Nod].empty()){

        int Y = G[Nod].front();

        S.push(Nod);

        G[Nod].pop_front();

        for(list<int>::iterator it = G[Y].begin(); it != G[Y].end(); it++){

            if(*it == Nod){
                G[Y].erase(it);
                break;
            }

        }

        Nod = Y;

    }

}

int main(){
    int Number = 0;
    Read();

    for(int i = 1; i <= N; ++i){
        if(G[i].size() % 2){
            fout << -1; return 0;
        }
    }
    S.push(1);
    do{

        int X = S.top();
        S.pop();
        Number++;
        Euler(X);
        if(Number != M + 1)
        fout << X <<" ";
    }while(S.empty() == false);

    return 0;
}