Cod sursa(job #921286)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 20 martie 2013 21:33:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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, 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);

    fin.close(); fout.close();
    return 0;
}