Cod sursa(job #2928448)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 octombrie 2022 22:22:33
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

vector <int> v[ 100011 ];
stack<int> q;

int from[ 500011 ];
bool ok[ 500011 ];
int egg[ 500011 ];
int n, m, x, y;
int k, p, nod;

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= m; i++ ) {
        cin >> x >> y;
        v[ x ].push_back( i );
        v[ y ].push_back( i );
        from[ i ] = x;
        egg[ i ] = y;
    }

    for( int i = 1; i <= n; i++ )
        if( v[ i ].size() & 1 ) {
            cout << -1;
            return 0;
        }

    q.push( 1 );
    while( q.empty() == false ) {
        k = q.top();
        if( v[ k ].empty() == false ) {
            nod = v[ k ].back();
            v[ k ].pop_back();
            if( ok[ nod ] == 0 ) {
                ok[ nod ] = 1;
                if( from[ nod ] == k )
                    p = egg[ nod ];
                else p = from[ nod ];
                q.push( p );
            }
        } else {
            q.pop();
            cout << k << ' ';
        }
    }
    return 0;
}