Cod sursa(job #2331309)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 29 ianuarie 2019 14:31:34
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
#define DIM_NOD 100005
#define DIM_MUCHII 500005
using namespace std;

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

int n, m;
vector< pair<int, int> > l[DIM_NOD];
stack<int> s;
int grad[DIM_NOD], F[DIM_MUCHII];
vector<int> sol;

int main()
{
    in>>n>>m;
    for( int i = 1; i <= m; i++ )
    {
        int from, to;
        in>>from>>to;

        l[from].push_back( { to, i } );
        l[to].push_back( { from, i } );

        grad[from]++; grad[to]++;
    }

    for( int nod : grad )
        if( nod % 2 == 1 )
        {
            out<<-1;
            return 0;
        }

    s.push(1);
    while( !s.empty() )
    {
        int nod = s.top();

        if( grad[nod] == 0  /*&& s.size() > 1*/ )
        {
            sol.push_back(nod);
            s.pop();
            continue;
        }

        while( F[ l[nod].back().second ] == 1 )
            l[nod].pop_back();

        int vecin = l[nod].back().first;
        s.push(vecin);
        grad[vecin]--; grad[nod]--;

        F[ l[nod].back().second ] = 1;
        l[nod].pop_back();

    }

    sol.pop_back();
    for( int i : sol )
        out<<i<<" ";

    return 0;
}