Cod sursa(job #2118796)

Utilizator CozmaCatalinCozma Catalin CozmaCatalin Data 31 ianuarie 2018 07:39:40
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXM 100005
#define MAXN 500005


using namespace std;

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

bool beenThere[MAXM];

vector < pair < int , int > > myVector[MAXN];
int Grad[MAXN];
stack < int > myStack;
vector < int > Answer;
int N, M;

void Read()
{
    in >> N >> M;

    for ( int i = 1; i <= M ; ++i)
    {
        int x,y;
        in >> x >> y;
        myVector[x].push_back(make_pair(y,i));
        myVector[y].push_back(make_pair(x,i));
        Grad[x]++;
        Grad[y]++;
    }


}


void Rezolv()
{
    for ( int i = 1; i <= N ; ++i)
        if(Grad[i]&1 || Grad[i] == 0)
    {
        out << -1;
        return;
    }

    myStack.push(1);
    while(!myStack.empty())
    {

        int nodCurent = myStack.top();

        if(myVector[nodCurent].size() > 0)
        {
            int x = myVector[nodCurent].back().first;
            int edge = myVector[nodCurent].back().second;
            myVector[nodCurent].pop_back();
            if(!beenThere[edge])
            {
                beenThere[edge] = true;
                myStack.push(x);
            }
        }
        else
        {
            myStack.pop();
            Answer.push_back(nodCurent);
        }
    }

    for ( int i = 0 ; i < Answer.size()-1 ; ++i) out << Answer[i] <<" ";
}
int main()
{
    Read();
     Rezolv();

}