Cod sursa(job #1036903)

Utilizator mvcl3Marian Iacob mvcl3 Data 19 noiembrie 2013 18:47:54
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <list>
#include <stack>
#define in "ciclueuler.in"
#define out "ciclueuler.out"
#define Max_Size 100009

std :: ifstream f(in);
std :: ofstream g(out);

int N, M;
int IO[Max_Size], X[Max_Size], Y[Max_Size], Sol[Max_Size];
bool Viz[Max_Size];

std :: list < int > V[Max_Size];
std :: stack < int > Stack;

inline void Read_Data()
{
    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X[i] >> Y[i];

        V[X[i]].push_back(Y[i]);
        V[Y[i]].push_back(X[i]);
        IO[X[i]] ++, IO[Y[i]] ++;
    }
}

inline bool  It_Is_Euler()
{
    for(int i = 1; i <= N; ++i) if(IO[i] % 2)   return 0;

    return 1;
}

inline void Euler(int nod)
{
    int nod1;
    std :: list < int > :: iterator it;

    while(!V[nod].empty())
    {
        nod1 = V[nod].front();
        V[nod].pop_front();

        Stack.push(nod);

        for(it = V[nod1].begin(); it != V[nod1].end(); ++it)
            if(*it == nod)
            {
                V[nod1].erase(it);
                break;
            }

        nod = nod1;
    }
}

inline void Solve()
{
    Stack.push(1);
    int K = 0;

    while(!Stack.empty())
    {
        int nod = Stack.top();
        Stack.pop();

        Euler(nod);
        ++K;

        if(K != M + 1)  g << nod << ' ';
    }
}

int main()
{
    Read_Data();

    if(It_Is_Euler())
        Solve();
    else
        g << "-1\n";

    g.close();
    return 0;
}