Cod sursa(job #1152767)

Utilizator mvcl3Marian Iacob mvcl3 Data 24 martie 2014 22:26:12
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define in "ciclueuler.in"
#define out "ciclueuler.out"
#define Max_Size 100009

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

int N, M;
std :: vector < int > V[Max_Size];

class Euler
{
    public :
        bool Is_it_a_Euler_Cicle()
        {
            for(int i = 1; i <= N; ++i)
                if(V[i].size() % 2) return 0;
            return 1;
        }

        void Route()
        {
            std :: stack < int > my_stack;
            my_stack.push(1);

            while(my_stack.size() > 0)
            {
                int nod = my_stack.top();
                if(V[nod].size() > 0)
                {
                    int a_nod = V[nod][0];
                    my_stack.push(a_nod);

                    V[nod].erase(V[nod].begin());
                    V[a_nod].erase( std :: find(V[a_nod].begin(), V[a_nod].end(), nod));
                }
                else    g << nod << ' ', my_stack.pop();
            }
        }

};

int main()
{
    f >> N >> M;
    for(int x, y, i = 1; i <= M; ++i)
    {
        f >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }

    Euler G;
    if(!G.Is_it_a_Euler_Cicle())    g << "-1\n";
    else                            G.Route();

    g.close();
    return 0;
}