Cod sursa(job #1254575)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 2 noiembrie 2014 22:39:36
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define Max_Size 100009

using namespace std;

const char iname[] = "ciclueuler.in";
const char oname[] = "ciclueuler.out";

int N, M;

vector < int > V[Max_Size];
stack < int > my_Stack;

inline void Read_Data()
{
    ifstream in( iname );

    in >> N >> M;
    for(int x, y, i = 1; i <= M; ++i) {
        in >> x >> y;

        V[x].push_back(y);
        V[y].push_back(x);
    }
}

inline bool Is_Valid()
{
    for(int i = 1; i <= N; ++i)
        if(V[i].size() % 2) return 0;

    return 1;
}

inline void Eulerian()
{
    ofstream out( oname );

    if(!Is_Valid()) out << "-1\n";
    else    {
        my_Stack.push(1);

        while(my_Stack.size() > 0) {
            int nod = my_Stack.top();

            if(V[nod].size() > 0)    {
                int vecin = V[nod][0];
                V[nod].erase( V[nod].begin() );

                my_Stack.push(vecin);

                V[vecin].erase( find( V[vecin].begin(), V[vecin].end(), nod) );
            }
            else    {
                out << nod << ' ';
                my_Stack.pop();
            }
        }
    }
}

int main()
{
    Read_Data();
    Eulerian();

    return 0;
}